Поиск совпадений цифр в списке чисел. Есть ли мысли?

← →
SergP. (2005-10-25 15:20) [0]

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

Например данная пара имеет 3 совпадения:
45236789315424
41896531386631

Пока кроме тупого перебора в голову ничего умного не приходит...
Есть ли какие-нить мысли по алгоритму такого поиска?

← →
Sandman29 © (2005-10-25 15:46) [1]

1. Отсортировать, найти совпадения в первой позиции.
2. Отбросить первую цифру.
3. Перейти на пункт 1 :)

← →
Sha © (2005-10-25 16:01) [2]

> Sandman29
не понял

← →
Sandman29 © (2005-10-25 16:08) [3]

>не понял

В массиве храним записи из
OriginalValue, CurrentValue, Counter

CurrentValue := OriginalValue;
Сортируем массив по CurrentValue.
Находим границы - индексы, на которых происходит смена первой цифры.
Для каждой группы увеличиваем Counter каждого элемента на (мощность группы - 1).
Убираем первую цифру у всех элементов в CurrentValue.
Повторяем.

В конце находим элемент с максимальным Counter. Берем исходное число из OriginalValue

← →
Sha © (2005-10-25 16:10) [4]

> В конце находим элемент с максимальным Counter
надо найти максимально близкую пару

← →
Sandman29 © (2005-10-25 16:12) [5]

Sha © (25.10.05 16:10) [4]

>надо найти максимально близкую пару

Тогда я балбес. Буду думать над новой (для меня :-) задачей.

← →
Sha © (2005-10-25 16:16) [6]

Похоже на перебор - O(n^2)

← →
Opilki_Inside © (2005-10-25 16:17) [7]

Жаль что числа заданы в десятичной системе... так можно было бы использовать побитывые сдвиги shr, shl

← →
Sha © (2005-10-25 16:20) [8]

> Opilki_Inside
Считай, что двоичные, 32 бита. От этого ничуть не легче.

← →
Sandman29 © (2005-10-25 16:21) [9]

Sha © (25.10.05 16:16) [6]

Да, согласен. Хотя можно попробовать отсортировать по сумме цифр. В худшем случае будет тот же O(n^2) + O(nlogn), в лучшем можно неплохо выиграть. в среднем тоже должен быть небольшой выигрыш.

← →
Sha © (2005-10-25 16:33) [10]

>Sandman29
>в среднем тоже должен быть небольшой выигрыш
хорошо бы это доказать для раномерного независимого распределения цифр :)

← →
Sandman29 © (2005-10-25 16:35) [11]

Sha © (25.10.05 16:33) [10]

Если бы у меня была такая курсовая, попробовал доказать бы :)

← →
MOA © (2005-10-25 16:54) [12]

Если задача позволяет, можно попытаться разменять память на скорость, например, во время сравнения (или заранее) строить списки (индексы) смысл которых "список чисел , в которых на К-той позиции стоит цифра Н" (числом 140 штук ;)). Тогда во время сравнения не нужно будет сравнивать числа, в которых в данной позиции не то.
Варианты "список чисел, в которых есть цифра 2", или "список чисел, в которых с 1-й по 6-ю позицию встречается цифра 3".
Если список целиком помещается в памяти - можно ещё как-нибудь память напрячь ;).

← →
MBo © (2005-10-25 16:54) [13]

Очень похоже:
http://algolist.manual.ru/sort/mqs/fast_strings6.php

← →
han_malign © (2005-10-25 17:04) [14]

Octree?

← →
Satirus (2005-10-25 17:08) [15]

похоже на коды пополнения карточек, там тоже обычно 14 чисел.
хочешь подобрать формулу, по которым они генерятся?%)

← →
Sha © (2005-10-25 17:16) [16]

Если карточки, то дело бесперспективное.
Существует куча алгоритмов таких, что следующий не угадаешь.

← →
Satirus (2005-10-25 17:49) [17]

> 2Sha © (25.10.05 17:16) [16]

а вообще есть. какие-то алгоритмы, которые хоть приблизительно могут вычислить закономерность генерации кодов?
вот у меня накопилось много карточек пополнения и я как настоящий программист, хочу подобрать функцию, по которой они генерятся%)))
не ради денег, интереса ради)))

← →
Igorek © (2005-10-25 18:02) [18]

> SergP. (25.10.05 15:20)
> Имеется довольно много 14-разрядных чисел.

Думаю можно предложить линейний алгоритм (и не один). Но напр. с квадратичной памятью. Насколько много чисел?

← →
Sha © (2005-10-25 18:35) [19]

> Satirus (25.10.05 17:49) [17]
> какие-то алгоритмы, которые хоть приблизительно могут вычислить закономерность генерации кодов?

Если бы генерил я, ты бы не вычислил :)
В смысле существуют такие алгоритмы генерации.

← →
Sha © (2005-10-25 18:36) [20]

> Igorek © (25.10.05 18:02) [18]
> Думаю можно предложить линейний алгоритм (и не один).

Пожалуйста, предложи хоть один :)

← →
Igorek © (2005-10-25 20:10) [21]

> Sha © (25.10.05 18:36) [20]

Ээ.. дома подумаю. :)

← →
Kerk © (2005-10-25 21:06) [22]

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

Решений кроме перебора пока не вижу. :(
Будет интересно проследить за веткой.

← →
SergP © (2005-10-25 21:51) [23]

> Satirus (25.10.05 17:08) [15]
> хочешь подобрать формулу, по которым они генерятся?%)

Смысл не в том что-бы найти какую-нить формулу генерации каких-нить кодов, а в том чтобы обнаружить наличие контрольных цифр, и алгоритма их расчета.

Когда-то искал такое в 8-разрядных числах (коды ЄДРПОУ), нашел сравнительно быстро.
Потом пришлось искать в 10-ти разрядных (ИНН) и 12-разрядных (код плат. НДС).
Программа ищущая метод формирования контрольных цифр работала бы довольно долго. Вот тогда и пришлось среди кучи кодов выбирать те, которые имеют наибольшее кол-во совпадений. После этого задача упрощалась. Например если прямой перебор занимал бы по времени 10^N, то после нахождения похожих кодов (например имеющих M совпадений) время поиска метода формирования контрольных цифр уменьшилось до 10^M + 10^(N-M)

Но в случае с 10-разрядными числами (кодами) у меня была БД с более чем 40000 таких кодов, так что там можно было отсортировать и выбрать с совпадением более чем половины цифр с начала числа. Сейчас же такого нет.
Вот и приходится отбирать максимально похожие...

← →
wicked © (2005-10-25 22:13) [24]

моё имхо - нету таких.... скорей всего, компания просто генерирует огромное кол-во псевдослучайных номеров, и записывает их в БД с пометкой, карточке какого номинала они присвоены.....
даже если есть автономные терминалы, выдающие код пополнения, то, скорей всего, они заранее "заряжены" последовательностью заранее сгенерированных кодов....
поэтому, такую вещь практически нереально взломать....

← →
Sha © (2005-10-26 00:49) [25]

> SergP © (25.10.05 21:51) [23]

> Смысл не в том что-бы найти какую-нить формулу генерации каких-нить
> кодов, а в том чтобы обнаружить наличие контрольных цифр, и алгоритма
> их расчета.

Во первых, не факт, что контрольные цифры жестко привязаны к месту,
место может определяться, например, по первым цифрам.
Во вторых, как бы ты определил алгоритм для такой простейшей схемы.
Первые 7 цифр используются как seed для генератора случайных чисел,
а следующие 7 (случайные) выработаны генератором.
Для любого генератора угадаешь? А если все цифры еще переставить?
Только полный перебор 10^7 комбинаций.

← →
MBo © (2005-10-26 07:38) [26]

Линейного алгоритма придумать не удалось.
Есть идея по реализации асимптотически квадратичного с ИМХО меньшим множителем, но нужна некая структура данных вроде быстрого разреженного двумерного массива, а может, чего-то графоподобного. Навскидку использовал StringList как ассоциативный массив, но скорость мала.

← →
Sha © (2005-10-26 09:47) [27]

> MBo
> Есть идея по реализации асимптотически квадратичного с ИМХО меньшим множителем
Поделишься?

← →
КаПиБаРа © (2005-10-26 10:15) [28]

Выводи промежуточные результаты. Вероятнее всего достаточное количество данных для дальнейшей работы наберется задолго до окончания полного перебора.

>Sha © (26.10.05 09:47) [27]
Вместо непосредственного вычисления расстояний Хемминга для всех пар - составляем таблицу 14(знакомест)*10(цифр), одним проходом по массиву занося в ее ячейки номера элементов, для которых на опред. знакоместе стоит данная цифра - у меня это списки.
Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс) в разреженный массив или хэш-таблицу , для каждой пары инкрементируем счетчик.

Пока не доделал c хэш-таблицей, и не могу сказать, хорошо ли это всё ;)

>Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс)

Разве не линейный? 140 списков по N элементов в каждом максимум

>Затем проходим по спискам, собирая все встреченные пары номеров (вот это квадратичный процесс)

Хотя да, торможу.

А если представить цифры как координаты в 14 мерном пространстве, а потом определить радиус и координаты сферы, в которой максимальная плотность точек... :)

ПМСМ, если решается практическая задача, необходимо иметь в виду, что алгоритмы более сложные чем перебор будут эффективны начиная с массивов >10000 записей (это "на глаз", по аналогии с сортировкой ;)) поскольку всё равно нужно "сравнить каждый с каждым" - в отличии от сортировки - а значит, алгоритм всё равно будет О(n**2), уменьшаем только коэффициент - а накладные расходы на построение списков и сравнения указателей съедят время на небольших массивах.

Да, поспешил я с выводами.. В голове сразу возникли было мысли как в [29], но при ближайшем рассмотрении оказалось - все же квадратичная скорость.

> MBo © (26.10.05 10:29) [29]
> Пока не доделал c хэш-таблицей, и не могу сказать, хорошо ли это всё ;)
Конечно хорошо. По идее (если не учитывать доп. расходы)
должно получиться в 10^2/10=10 раз быстрее.

> MBo ©
Твой способ без хэша будет быстрее,
а экономии памяти по сравнению с обычной таблицей хэш почти не дает (0.9^14=0.23).

>Sha © (26.10.05 12:16) [36]
>Твой способ без хэша будет быстрее,

Да, я уже осознал. Поначалу с 6-7 разрядными числами баловался, для них наполнение таблицы связей - не более трети, поэтому и динамическую структуру захотелось.

const N = 500;//5000 //попарное сравнение (медленное ) procedure TForm1.Button2Click(Sender: TObject); var A: array of Int64; l1, l2: Int64; i, j, k, ii, jj, Cnt, Mx: Integer; t: DWord; begin SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do for j := i + 1 to N - 1 do begin l1 := A[i]; l2 := A[j]; Cnt := 0; for k := 1 to 14 do begin if (l1 mod 10) = (l2 mod 10) then Inc(Cnt); l1 := l1 div 10; l2 := l2 div 10; end; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end; //матричный метод procedure TForm1.Button3Click(Sender: TObject); const Sz = 14; var A: array of Int64; l: Int64; i, j, k, ii, jj, AA, BB, Mx: Integer; M: array[1..Sz, 0..9] of TList; Conn: array of array of Byte; t: DWord; begin SetLength(Conn, N, N); SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; for i := 1 to Sz do for j := 0 to 9 do M[i, j] := TList.Create; t := GetTickCount; for k := 0 to N - 1 do begin l := A[k]; for i := 1 to Sz do begin M[i, l mod 10].Add(Pointer(k)); l := l div 10; end; end; for i := Sz downto 1 do for j := 0 to 9 do if M[i, j].Count > 1 then begin for k := 0 to M[i, j].Count - 2 do begin AA := Integer(M[i, j][k]); for ii := k + 1 to M[i, j].Count - 1 do begin BB := Integer(M[i, j][ii]); if AA < BB then Inc(Conn[AA, BB]) else Inc(Conn[BB, AA]); end; end; end; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do for j := i + 1 to N - 1 do if Conn[i, j] > Mx then begin Mx := Conn[i, j]; ii := i; jj := j; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); for i := 1 to Sz do for j := 0 to 9 do M[i, j].Free; end;

> MBo © (26.10.05 13:22) [38]

Код еще не смотрел. Запустил, получил:

119656 мс: 10 совпадений: 253 52449711333529 2212 52449701333918 2813 мс: 10 совпадений: 253 52449711333529 2212 52449701333918

По теории разница должна быть в 10 раз, у тебя больше, чем в 40.
В чем дело?

Если из цикла вынести лишнее, простой перебор ускоряется в 2 раза

procedure TForm1.Button3Click(Sender: TObject); //попарное сравнение (чуть быстрее) var A: array of Int64; l1, l2: Int64; i, j, k, ii, jj, Cnt, Mx: Integer; t: DWord; md: array[1..14] of integer; begin SetLength(A, N); RandSeed := 2; for i := 0 to N - 1 do begin A[i] := 10000000000000 + Int64(1000000) * Random(90000000) + Random(1000000); // Memo1.Lines.Add(Format("%d %d", [i, A[i]])); end; t := GetTickCount; Mx := 0; ii := 0; jj := 0; for i := 0 to N - 2 do begin l1 := A[i]; for k := 1 to 14 do begin md[k]:=l1 mod 10; l1 := l1 div 10; end; for j := i + 1 to N - 1 do begin l2 := A[j]; Cnt := 0; for k := 1 to 14 do begin Inc(Cnt,ord(l2 mod 10=md[k])); l2 := l2 div 10; end; if Cnt > Mx then begin Mx := Cnt; ii := i; jj := j; end; end; end; Memo1.Lines.Add(Format("%d мс:", [GetTickCount - t])); Memo1.Lines.Add(Format("%d совпадений:", [Mx])); Memo1.Lines.Add(Format("%d %d", [ii, A[ii]])); Memo1.Lines.Add(Format("%d %d", [jj, A[jj]])); end;

Поиск совпадений цифр в списке чисел. Есть ли мысли? Найти похожие ветки