Способ проверки, являются ли цифры num1 цифрами в num2, без проверки каждой цифры?

Question

Допустим, я угадал лотерейный номер:

1689

И как работает лотерея, порядок цифр не имеет значения, если цифры совпадают 1: 1 с цифрами в фактическом выигрышном номере лотереи.

Итак, номер 1689 будет выигрышным номером лотереи с:

1896, 1698, 9816 и т. Д.

Пока каждая цифра в вашем предположении присутствует в целевом числе, вы выигрываете в лотерею.

Есть ли математический способ, которым я могу это сделать?

Я решил эту проблему с помощью цикла O (N ^ 2), проверяющего каждую цифру против каждой цифры номера выигрышной лотереи (разделяя их по модулю). Что хорошо, это работает, но я хочу знать, есть ли какие-нибудь изящные математические трюки, которые я могу сделать.

Например, сначала ... Я подумал, что могу быть хитрым и просто взять сумму и произведение каждой цифры в обоих числах, и если они совпадают, то вы выиграли.

^ Как вы думаете, это сработает?

Тем не менее, я быстро опроверг это, когда обнаружил, что лотерейное предположение: 222 и 124 имеют разные цифры, но один и тот же продукт и сумму.

Кто-нибудь знает какие-нибудь математические приемы, которые я могу использовать, чтобы быстро определить, соответствуют ли цифры в num1 цифрам в num2, независимо от порядка?

Answer 1

Как насчет прохождения каждого числа и подсчета количества появлений каждой цифры (в два разных массива из 10 элементов)? После того, как вы сделали суммирование, сравните количество каждой цифры. Поскольку вы смотрите на каждую цифру только один раз, это O (N).

Код будет выглядеть примерно так:

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

Приведенный выше код делает предположение, что предположения и фактические значения являются символьными строками. если они содержали действительные цифры, то вы можете просто пропустить бизнес - '0'.

Вероятно, существуют оптимизации, которые позволили бы занять меньше места или завершиться раньше, но это довольно простой пример подхода O (N).

Кстати, как я уже упоминал в комментарии, сравнение умножения / суммы определенно не будет работать из-за нулей. Рассмотрим 0123 и 0222. Произведение равно 0, сумма равна 6 в обоих случаях.

Answer 2

Разделить на массив, отсортировать массив, объединить в строку, сравнить строки.

(Не знаю, математический трюк)

Answer 3

Вы можете поместить цифры в массив, отсортировать массив, а затем сравнить элементы массива по элементам. Это даст вам сложность O (NlogN), которая лучше, чем O (N ^ 2).

Answer 4

Для каждой цифры d умножьте на (d + 1) -ое простое число.

Это более математично, но менее эффективно, чем методы сортировки или корзины. На самом деле это скрытый метод ведра.

Answer 5

Если N может стать большим, ответом будет сортировка цифр.

Поскольку цифры равны 0,9, вы можете подсчитать количество вхождений каждой цифры ответа лотереи в массиве [0.,9].

Для сравнения вы можете вычесть 1 для каждой цифры, с которой вы столкнулись в догадке. Когда вы сталкиваетесь с цифрой, где счет уже равен 0, вы знаете, что догадка отличается. Когда вы наберете все цифры, предположение будет таким же (при условии, что в предположении столько цифр, сколько в ответе на лотерею).

Answer 6

Одним из симпатичных решений является использование варианта Хеширования Zobrist . (Да, я знаю, что это излишне, а также вероятностно, но эй, это "умно".)

Инициализировать массив из десяти элементов a[0..9] для случайных целых чисел. Затем для каждого числа d[] вычислите сумму a[d[i]]. Если числа содержали одинаковые цифры, результирующие числа будут равны; с высокой вероятностью (~ 1 в количестве возможных целых чисел), верно и обратное.

(Если вы знаете, что всего будет не более 10 цифр, то вы можете использовать фиксированные числа 1, 10, 100, ... вместо случайных чисел для гарантированного успеха. Это сортировка сегментов в не слишком много маскировки.)

Answer 7

Просто для удовольствия, и мыслить нестандартно, а не сортировать и другими способами, делать вещь удаления. Если строка результатов пуста, у вас есть победитель!

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

Это работает и с повторяющимися числами ..

Answer 8

Если повторяющиеся цифры не разрешены (хотя не уверен, что это так), используйте 10-битное двоичное число. Самый старший бит представляет цифру 9, а младший бит представляет цифру 0. Прорабатывайте каждое число по очереди и меняйте соответствующий бит для каждой найденной цифры

Итак, 1689 будет: 1101000010

и 9816 также будут: 1101000010

тогда XOR или вычитание оставят 0, если вы выиграли

Это просто простая форма группирования

Answer 9

Создать массив из 10 целых чисел с подпиской [0 .. 9].

Инициализировать каждый элемент другим простым числом

Установить продукт на 1.

Используйте каждую цифру из числа, чтобы вписать в массив, вытащите простое число и умножьте произведение на него.

Это дает вам уникальное представление, которое не зависит от порядка цифр.

Выполните ту же процедуру для другого номера.

Если уникальные представления совпадают, то исходные числа совпадают.

Answer 10

Я краду ответ от Юлия, и звездный синий (upvote их)

Bucketing является самым быстрым в стороне от O (1)

lottonumbers == mynumbers;

Сортировка O (nlog2n)

Bucketsort - это алгоритм O (n).

Так что все, что вам нужно сделать, это сделать это дважды (один раз для ваших чисел, один раз для целевого набора), и если числа цифр складываются, то они совпадают. Любая сортировка - это дополнительные издержки, которые в этом случае не нужны.

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

Не самый красивый код, я признаю.