for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

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

Сообщений: 2880
Откуда: Е-бург
Дата: 12.07.16 08:03:14ОтветитьЦитировать
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

Сообщений: 5063
Дата: 12.07.16 08:29:56ОтветитьЦитировать
Так нас интересует сумма всех дробей. Предположим у нас есть числа 111111Х3 и 11111166. Какая бы цифра ни была на месте Х -

1/Х + 1/3 != 1/6 + 1/6

Впрочем, 3 можно заменить на Y. Тогда 1/Х + 1/Y = 1/6 + 1/6 только в том случае, если X = Y = 6



Исправлено: spinz, 12.07.16 08:33
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 31338
Дата: 12.07.16 11:52:12ОтветитьЦитировать
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




Исправлено: Igor Korolyov, 12.07.16 11:58
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5063
Дата: 12.07.16 11:59:22ОтветитьЦитировать
Ага.

А если брать квадраты обратных чисел?
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 31338
Дата: 12.07.16 12:14:31ОтветитьЦитировать
Лучше, но всё равно конфликтов достаточно много.
Шоб не парится, вот тестовая шняга - генератор всех сочетаний из 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

Сообщений: 5063
Дата: 12.07.16 13:50:25ОтветитьЦитировать
В качестве хэш-функции здесь конечно самое правильное придумать какой-то быстровычисляемый полином, не дающий коллизий. Может подойдут и просто небольшие степени. Квадраты очевидно не подходят, а кубы и выше лень проверять.

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



Исправлено: spinz, 12.07.16 13:57
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 31338
Дата: 12.07.16 14:01:15ОтветитьЦитировать
Полагаю что по временнЫм затратам всё это сравнимо с банальной "сортировкой набора". Естественно, выполняемой сишным кодом, а не фоксовыми конструкциями с циклами Т.е. по сути приводить все наборы к одному из "каноничных" видов сочетания - либо элементы по возрастанию, либо по убыванию.
Я то схитрил, заменив цикл по элементам на OCCURS - цикл реализованный на си - но для других случаев так просто не отскочить IMHO.
P.S. И это, как ранее отмечали, будет НЕ хэш. Хэш по своему определению предполагает коллизии. А взаимно-однозначная (двунаправленная в терминах "сочетания с повторениями") трансформация это уже не хэш...
P.P.S. Произведение 8-ми простых чисел (10-е простое число это 29) это уже весьма большое число, и растёт экспоненциально при росте числа элементов в наборе (при том требует абсолютной точности - потеря "младших разрядов" абсолютно недопустима). Мой вариант (при вычислении степени в зависимости от числа элементов) растёт по логарифмическому закону, если я ничего не путаю.


------------------
WBR, Igor




Исправлено: Igor Korolyov, 12.07.16 14:36
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5063
Дата: 12.07.16 14:12:15ОтветитьЦитировать
spinz
Можно каждой цифре поставить в соответствие простое число: 0 - 2, 1 - 3, 2 - 5, 4 - 7 и т.д.

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

Полагаю, что перемножение n элементов при небольших n все же быстрей сортировки
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5063
Дата: 12.07.16 15:12:00ОтветитьЦитировать
Думаю можно просто проверить

Максимальное число в моем варианте - 99999999 = 29^8 = 500246412961. Хз конечно как 32битный компилятор на 32битном проце будет реализовать такое умножение (и будет ли вообще), а для 64 битного кода хватит и обычных регистров CPU.

P.S.
Но все это конечно ерунда. Можно просто суммировать, поставив в соответствие каждой цифре степень двойки: 0 = 1, 1 = 2, 2 = 4, 3 = 8 и т.д.
Это точно быстрей всего.

Хотя нет, двойки мало, 9 вполне подойдет



Исправлено: spinz, 12.07.16 15:23
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Igor Korolyov

Сообщений: 31338
Дата: 12.07.16 15:39:19ОтветитьЦитировать
Число потребных бит для твоего числа это
? 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

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

Re: Выбрать числа одного цифрового состава
Simple777

Сообщений: 18799
Дата: 13.07.16 11:44:24ОтветитьЦитировать
Дык у нас по большому счету пока не вычислительная техника, а так - детские игрушки, если сравнить хотя бы с генетическими алгоритмами по развитию сперматазоида до состояния новорожденного. Наверняка в этом алгоритме используются миллионы независимых параметров и миллиардная вложенность в циклы, что позволяет достигать различных рекомбинаций при развитии организма. А тут у нас 20 чисел, и уже надо использовать специальную технику. [sm128]
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Igor Korolyov

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


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
spinz

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

Re: Выбрать числа одного цифрового состава
Igor Korolyov

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


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
spinz

Сообщений: 5063
Дата: 14.07.16 11:26:23ОтветитьЦитировать
А, значит я не так понял твою фразу.
Ratings: 0 negative/0 positive

Re: Выбрать числа одного цифрового состава
Foxtrot

Сообщений: 3264
Откуда: Бишкек
Дата: 18.07.16 20:40:20ОтветитьЦитировать
это лишь как вариант задачи forum.foxclub.ru


------------------
P.S. будете проходить мимо, не стесняйтесь, проходите
Ratings: 0 negative/0 positive



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

On-line: 46 and Guests: 46


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