:: Игры Разума
Re: Выбрать числа одного цифрового состава
pasha_usue

Сообщений: 3647
Откуда: Е-бург
Дата регистрации: 06.10.2006
spinz
2/6 = 1/6 + 1/6. А какие другие две дроби с натуральным знаменателем не больше 9 дадут в сумме 1/3?
Т.е. может быть 1/9 + 1/9 + 1/9 = 1/3. Но тогда и к сумме 1/6 + 1/6 мы должны прибавить третью дробь.
Вот я и говорю. Как различить, две шестерки было, или одна тройка? Две четверки было, или одна двойка? А может быть, две восьмерки было и одна четверка?
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
Ага.

А если брать квадраты обратных чисел?
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Лучше, но всё равно конфликтов достаточно много.
Шоб не парится, вот тестовая шняга - генератор всех сочетаний из 10 по 8, гарантированно уникальная функция, и заглушка под тестируемую. Из res потом можно вынимать конфликты (например просто группируя по hash2 с HAVING COUNT(*) > 1). Для тестируемой функции не стоит забывать про CAST - а то м.б. ненужное усечение размера поля
CREATE CURSOR dat (num C(8))
LOCAL lnK, lnN, lcNumber
lnK = 8
lnN = 10
lcNumber = GetInitialComb(m.lnK)
INSERT INTO dat (num) VALUES (m.lcNumber)
DO WHILE GetNextComb(@lcNumber, lnN, lnK)
INSERT INTO dat (num) VALUES (m.lcNumber)
ENDDO
SELECT COUNT(*), GetCombNumCount(num) hash, GetHash2(num) hash2 FROM dat ;
GROUP BY 2, 3 ;
INTO CURSOR res
PROCEDURE GetInitialComb(tnK)
RETURN REPLICATE("0", m.tnK)
PROCEDURE GetNextComb(tcInput, tnN, tnK)
LOCAL lnJ
IF VAL(SUBSTR(m.tcInput, m.tnK, 1)) < (m.tnN - 1)
tcInput = LEFT(m.tcInput, m.tnK - 1) + STR(VAL(SUBSTR(m.tcInput, m.tnK, 1)) + 1, 1)
RETURN .T.
ENDIF
FOR lnJ = m.tnK - 1 TO 1 STEP -1
IF VAL(SUBSTR(m.tcInput, m.lnJ, 1)) != (m.tnN - 1)
tcInput = LEFT(m.tcInput, m.lnJ - 1) + REPLICATE(STR(VAL(SUBSTR(m.tcInput, m.lnJ, 1)) + 1, 1), m.tnK - m.lnJ + 1)
RETURN .T.
ENDIF
ENDFOR
RETURN .F.
ENDPROC
PROCEDURE GetCombNumCount(tcInput)
RETURN ;
OCCURS("0", m.tcInput)+;
OCCURS("1", m.tcInput)*10+;
OCCURS("2", m.tcInput)*100+;
OCCURS("3", m.tcInput)*1000+;
OCCURS("4", m.tcInput)*10000+;
OCCURS("5", m.tcInput)*100000+;
OCCURS("6", m.tcInput)*1000000+;
OCCURS("7", m.tcInput)*10000000+;
OCCURS("8", m.tcInput)*100000000+;
OCCURS("9", m.tcInput)*1000000000
PROCEDURE GetHash2(tcNum)
RETURN ...


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
В качестве хэш-функции здесь конечно самое правильное придумать какой-то быстровычисляемый полином, не дающий коллизий. Может подойдут и просто небольшие степени. Квадраты очевидно не подходят, а кубы и выше лень проверять.

P.S.
Можно каждой цифре поставить в соответствие простое число: 0 - 2, 1 - 3, 2 - 5, 4 - 7 и т.д. Произведение соответствующих простых чисел будет уникальным хэшем.



Исправлено 1 раз(а). Последнее : spinz, 12.07.16 13:57
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
spinz
Можно каждой цифре поставить в соответствие простое число: 0 - 2, 1 - 3, 2 - 5, 4 - 7 и т.д.

Igor Korolyov
Полагаю что по временнЫм затратам всё это сравнимо с банальной "сортировкой набора"

Полагаю, что перемножение n элементов при небольших n все же быстрей сортировки
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
Хм, подобрать сходу полином невысокой степени, гарантирующий уникальность каждой комбинации цифр, нифига не получилось. Хотя это определенно самый правильный путь для решения данной задачи с достаточно большим количеством цифр. Предложенное ИК решение брать десятичную степень (хотя для 8 цифр можно степень 9) для каждой цифры все равно упирается в разрядность - скажем для 20 значного числа уже не прокатит даже на 64битной системе. Да и основание степени для 20 значного числа нужно брать другое, больше 20.
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
Simple777

Сообщений: 33855
Дата регистрации: 05.11.2006
Дык у нас по большому счету пока не вычислительная техника, а так - детские игрушки, если сравнить хотя бы с генетическими алгоритмами по развитию сперматазоида до состояния новорожденного. Наверняка в этом алгоритме используются миллионы независимых параметров и миллиардная вложенность в циклы, что позволяет достигать различных рекомбинаций при развитии организма. А тут у нас 20 чисел, и уже надо использовать специальную технику. [sm128]
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Степени 10-ки это я для простоты взял Так нужны степени (K+1) - это если пытаться минимизировать получаемые числа.
Но эффективнее считать и упаковывать используя битовые операции (сдвиг и битовое или) и, соответственно, "ближайшие сверху" степени двойки. Для "20-значного числа" - равно как и для любого другого вплоть до 31-значного нужно всего по 5 бит на каждую "цифру", или 50 бит всего. И даже все сочетания вплоть до 63-разрядных вполне умещаются в 60 бит (по 6 бит на каждый "счётчик").
Полином с округлением/отсечением старших разрядов (как это используется в классических хэш-функциях), как я понимаю, не даёт необходимой в данном случае уникальности. Т.е. он может, наверное, сработать в каком-то частном случае (типа для 8-ми элементного), но при минимальном изменении условий (N или K) он уже не подойдёт. Варианты с сортировкой, равно как и с "подсчётом количества элементов каждого типа" работает всегда - но надо посмотреть при каких условиях какой из этих вариантов будет эффективнее. При том что "строка символов-чисел" это в общем случае весьма неэффективное решение для хранения сочетания из 10 элементов. Вот если использовать каждый байтик по плешку, т.е. рассматривать сочетания их 256-ти элементов, тогда уж совсем другое дело - это будет оптимальное решение (без использования сжатия/архивирования)


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
Igor Korolyov
Для "20-значного числа" - равно как и для любого другого вплоть до 31-значного нужно всего по 5 бит на каждую "цифру", или 50 бит всего.
Строго говоря, это верно только небольшого класса 31-значных "чисел" - тех, где нет повторяющихся цифр. 5-ю битами можно описать позицию только одной цифры в числе.
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Тут не надо описывать позиции - это задача о сочетаниях с повторениями - т.е. важно лишь сколько элементов-цифр каждого вида находится в сочетании - порядок значения не имеет. А максимальное число таких вхождений, естественно, равно размеру выборки. Число счётчиков же равно количеству возможных элементов - для "цифровых" выборок это 10.


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5263
Дата регистрации: 21.01.2016
А, значит я не так понял твою фразу.
Ratings: 0 negative/0 positive
Re: Выбрать числа одного цифрового состава
Foxtrot
Автор

Сообщений: 3408
Откуда: Куда:
Дата регистрации: 25.04.2003
это лишь как вариант задачи forum.foxclub.ru


------------------
Мойте ноги, моя ноги вы моете и руки
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 1 (Гостей: 1)

© 2000-2024 Fox Club 
Яндекс.Метрика