Re: Выбрать числа одного цифрового состава | |
---|---|
pasha_usue Сообщений: 3647 Откуда: Е-бург Дата регистрации: 06.10.2006 |
Вот я и говорю. Как различить, две шестерки было, или одна тройка? Две четверки было, или одна двойка? А может быть, две восьмерки было и одна четверка? |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Так нас интересует сумма всех дробей. Предположим у нас есть числа 111111Х3 и 11111166. Какая бы цифра ни была на месте Х -
1/Х + 1/3 != 1/6 + 1/6 Впрочем, 3 можно заменить на Y. Тогда 1/Х + 1/Y = 1/6 + 1/6 только в том случае, если X = Y = 6 Исправлено 1 раз(а). Последнее : spinz, 12.07.16 08:33 |
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
88888888, 99988886 и 99999966 например
8*(1/8)=3*(1/9)+4*(1/8)+(1/6)=6*(1/9)+2*(1/6) = 1 P.S. А у хеша 2.5 вообще 35 порождающих вариантов 12366999,12368888,12446999,12448888,12466688,12666666,13336999,13338888,13344999,13346688,13366666,13444688,13446666,13555556,14444488,14444666,14455555,22226999,22228888,22233999,22234688,22236666,22244488,22244666,22255555,22333488,22333666,22334466,22344446,22444444,23333366,23333446,23334444,33333336,33333344 ------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 12.07.16 11:58 |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Ага.
А если брать квадраты обратных чисел? |
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Лучше, но всё равно конфликтов достаточно много.
Шоб не парится, вот тестовая шняга - генератор всех сочетаний из 10 по 8, гарантированно уникальная функция, и заглушка под тестируемую. Из res потом можно вынимать конфликты (например просто группируя по hash2 с HAVING COUNT(*) > 1). Для тестируемой функции не стоит забывать про CAST - а то м.б. ненужное усечение размера поля
------------------ WBR, Igor |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
В качестве хэш-функции здесь конечно самое правильное придумать какой-то быстровычисляемый полином, не дающий коллизий. Может подойдут и просто небольшие степени. Квадраты очевидно не подходят, а кубы и выше лень проверять.
P.S. Можно каждой цифре поставить в соответствие простое число: 0 - 2, 1 - 3, 2 - 5, 4 - 7 и т.д. Произведение соответствующих простых чисел будет уникальным хэшем. Исправлено 1 раз(а). Последнее : spinz, 12.07.16 13:57 |
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Полагаю что по временнЫм затратам всё это сравнимо с банальной "сортировкой набора". Естественно, выполняемой сишным кодом, а не фоксовыми конструкциями с циклами Т.е. по сути приводить все наборы к одному из "каноничных" видов сочетания - либо элементы по возрастанию, либо по убыванию.
Я то схитрил, заменив цикл по элементам на OCCURS - цикл реализованный на си - но для других случаев так просто не отскочить IMHO. P.S. И это, как ранее отмечали, будет НЕ хэш. Хэш по своему определению предполагает коллизии. А взаимно-однозначная (двунаправленная в терминах "сочетания с повторениями") трансформация это уже не хэш... P.P.S. Произведение 8-ми простых чисел (10-е простое число это 29) это уже весьма большое число, и растёт экспоненциально при росте числа элементов в наборе (при том требует абсолютной точности - потеря "младших разрядов" абсолютно недопустима). Мой вариант (при вычислении степени в зависимости от числа элементов) растёт по логарифмическому закону, если я ничего не путаю. ------------------ WBR, Igor Исправлено 1 раз(а). Последнее : Igor Korolyov, 12.07.16 14:36 |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Полагаю, что перемножение n элементов при небольших n все же быстрей сортировки |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Думаю можно просто проверить
Максимальное число в моем варианте - 99999999 = 29^8 = 500246412961. Хз конечно как 32битный компилятор на 32битном проце будет реализовать такое умножение (и будет ли вообще), а для 64 битного кода хватит и обычных регистров CPU. P.S. Но все это конечно ерунда. Можно просто суммировать, поставив в соответствие каждой цифре степень двойки: 0 = 1, 1 = 2, 2 = 4, 3 = 8 и т.д. Это точно быстрей всего. Хотя нет, двойки мало, 9 вполне подойдет Исправлено 4 раз(а). Последнее : spinz, 12.07.16 15:23 |
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Число потребных бит для твоего числа это
? LOG(29)*m.lnK/LOG(2) уже для 7-элементного сочетания не хватит int32 а для 14-ти элементного и int64 Для моего - LOG(m.lnK+1)*10/LOG(2) - для "малых" размеров оно даже хуже, но потом быстро реабилитируется По сути нужно выделить столько бит, сколько нужно для хранения числа K десять раз. Самое "тяжёлое" в этом алгоритме, я полагаю, это именно разбивка строки на отдельные числа. Если бы писал на си, то просто завёл массив на 10 чисел и за 1 проход посчитал сколько кого там в строке, инкрементируя нужный элемент. Впрочем, если по задаче будет меняться не только K но ещё и N ("алфавит" - т.е. набор элементов из которых идёт выборка) то может оказаться выгоднее и нечто совсем другое - та же сортировка элементов - благо qsort несложен ------------------ WBR, Igor |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Хм, подобрать сходу полином невысокой степени, гарантирующий уникальность каждой комбинации цифр, нифига не получилось. Хотя это определенно самый правильный путь для решения данной задачи с достаточно большим количеством цифр. Предложенное ИК решение брать десятичную степень (хотя для 8 цифр можно степень 9) для каждой цифры все равно упирается в разрядность - скажем для 20 значного числа уже не прокатит даже на 64битной системе. Да и основание степени для 20 значного числа нужно брать другое, больше 20.
|
Re: Выбрать числа одного цифрового состава | |
---|---|
Simple777 Сообщений: 33855 Дата регистрации: 05.11.2006 |
Дык у нас по большому счету пока не вычислительная техника, а так - детские игрушки, если сравнить хотя бы с генетическими алгоритмами по развитию сперматазоида до состояния новорожденного. Наверняка в этом алгоритме используются миллионы независимых параметров и миллиардная вложенность в циклы, что позволяет достигать различных рекомбинаций при развитии организма. А тут у нас 20 чисел, и уже надо использовать специальную технику.
|
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Степени 10-ки это я для простоты взял Так нужны степени (K+1) - это если пытаться минимизировать получаемые числа.
Но эффективнее считать и упаковывать используя битовые операции (сдвиг и битовое или) и, соответственно, "ближайшие сверху" степени двойки. Для "20-значного числа" - равно как и для любого другого вплоть до 31-значного нужно всего по 5 бит на каждую "цифру", или 50 бит всего. И даже все сочетания вплоть до 63-разрядных вполне умещаются в 60 бит (по 6 бит на каждый "счётчик"). Полином с округлением/отсечением старших разрядов (как это используется в классических хэш-функциях), как я понимаю, не даёт необходимой в данном случае уникальности. Т.е. он может, наверное, сработать в каком-то частном случае (типа для 8-ми элементного), но при минимальном изменении условий (N или K) он уже не подойдёт. Варианты с сортировкой, равно как и с "подсчётом количества элементов каждого типа" работает всегда - но надо посмотреть при каких условиях какой из этих вариантов будет эффективнее. При том что "строка символов-чисел" это в общем случае весьма неэффективное решение для хранения сочетания из 10 элементов. Вот если использовать каждый байтик по плешку, т.е. рассматривать сочетания их 256-ти элементов, тогда уж совсем другое дело - это будет оптимальное решение (без использования сжатия/архивирования) ------------------ WBR, Igor |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
Строго говоря, это верно только небольшого класса 31-значных "чисел" - тех, где нет повторяющихся цифр. 5-ю битами можно описать позицию только одной цифры в числе. |
Re: Выбрать числа одного цифрового состава | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Тут не надо описывать позиции - это задача о сочетаниях с повторениями - т.е. важно лишь сколько элементов-цифр каждого вида находится в сочетании - порядок значения не имеет. А максимальное число таких вхождений, естественно, равно размеру выборки. Число счётчиков же равно количеству возможных элементов - для "цифровых" выборок это 10.
------------------ WBR, Igor |
Re: Выбрать числа одного цифрового состава | |
---|---|
spinz Сообщений: 5263 Дата регистрации: 21.01.2016 |
А, значит я не так понял твою фразу.
|
Re: Выбрать числа одного цифрового состава | |
---|---|
Foxtrot Автор Сообщений: 3408 Откуда: Куда: Дата регистрации: 25.04.2003 |
|
© 2000-2024 Fox Club  |