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

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

Выбрать числа одного цифрового состава
sphinx
Автор

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 05.07.16 17:14:13ОтветитьЦитировать
Есть список 8-значных чисел. Нужно придумать алгоритм (желательно проще/эффективнее), чтобы выбрать все числа, имеющие одинаковый состав цифр (например, числа 12345, 54321, 13245, 13254, 32451 - относятся к одной группе, так как состав цифр, пусть и на разных позициях - одинаков).

Выводить предлагаю таким образом - если для числа еще не создана новая цифровая группа - число заносится в первый столбец, если встретилось 2-й, 3-й... N-й раз - помещается во 2-й, 3-й,... N-й столбец. Столбцы называю условно, пусть собирается группа через запятую - каждая группа в своей строке.


P.S. В архиве CSV-файл с набором 8-значных чисел, сделать из него таблицу/курсор, полагаю, труда не составит.


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)




Исправлено: sphinx, 05.07.16 17:18
Ratings: 0 negative/0 positive


Вложения:
[numbers1.zip (4.5KB)]  

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

Сообщений: 12942
Дата: 05.07.16 17:19:48ОтветитьЦитировать
1+2+3+4+5 = 5+4+3+2+1 = 1+3+2+4+5 = 1+3+2+5+4 = 3+2+4+5+1

Не то,


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)




Исправлено: PaulWist, 05.07.16 17:23
Ratings: 0 negative/0 positive

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

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 05.07.16 17:27:41ОтветитьЦитировать
PaulWist
Не то,

Разумеется. На примере двузначных чисел: 13 и 22 - РАЗНЫЕ группы чисел, хотя сумма цифр у них одинаковая.


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

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

Сообщений: 5046
Откуда: Подмосковье
Дата: 05.07.16 19:52:08ОтветитьЦитировать
Подозреваю, без сортировки символов в числовом выражении обойтись будет сложно. Условно говоря, 13254 должно преобразоваться в 12345 (или наоборот), тогда сравниваем как строки.


------------------
"Здесь я, братцы, сдержу матерщину, и скажу только "... мать!"" (с) Шаов
Ratings: 0 negative/0 positive

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

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 05.07.16 20:06:10ОтветитьЦитировать
SoccerStudio
Подозреваю, без сортировки символов в числовом выражении обойтись будет сложно.

Да, это одно из решений. Но сортировка ВСЕХ чисел - относительно не быстрая операция, хотя на 1000/10000 чисел должна пролететь без серьезных временных затрат.

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


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

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

Сообщений: 2543
Откуда: Рига
Дата: 05.07.16 22:20:05ОтветитьЦитировать
Как идея. Доказывать, что это всегда даст правильный результат не буду.

RAND(-1)  
  cnt = 100000  
  CREATE CURSOR tmp (f1 c(8))  
  FOR i =  1 TO cnt  
  	INSERT INTO tmp VALUES (PADL(INT(RAND()*100000000), 8 ,"0"))  
  NEXT  
    
  SELECT f1, 0000000 + hash(f1) as hash FROM tmp ORDER BY 2 INTO CURSOR tmp2  
    
  BROWSE nowait  
    
  RETURN  
    
  FUNCTION hash  
  LPARAMETERS m.st  
  LOCAL m.s1, m.s2, m.s3, m.cf  
  m.s1 = 0  
  m.s2 = 0  
  m.s3 = 0  
  FOR m.i = 1 TO 8  
  	m.cf = INT(VAL(SUBSTR(m.st, m.i, 1)))  
  	m.s1 = m.s1 + m.cf  
  	m.s2 = m.s2 + m.cf * m.cf  
  	m.s3 = m.s3 + m.cf * m.cf * m.cf  
  NEXT  
  RETURN m.s1 * 10000000 + m.s2 * 1000 + m.s3
Ratings: 0 negative/0 positive

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

Сообщений: 31997
Дата: 06.07.16 01:33:14ОтветитьЦитировать
leonid
Как идея. Доказывать, что это всегда даст правильный результат не буду.
А оно и не даст всегда правильный результат
? hash("11124458") = hash("11222477")
Если быть чуть точнее, то на всём массиве "сочетаний с повторениями" из 10-ти по 8 эта функция даёт 24% коллизий. 5816 из общих 24310 таких сочетаний имеют дубликаты (и даже "трипликаты и квадропликаты") этого хэша. Да и вообще в данной задаче "хэш" не применим - нужно гарантировано уникально идентифицировать каждую из перестановок одного и того же сочетания.

Тупо в лоб для 9 и менее разрядных чисел (в т.ч. 8-разрядных по условию задачи) подойдёт такая функция:
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


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

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

Сообщений: 19924
Дата: 06.07.16 06:00:27ОтветитьЦитировать
Как я понимаю, можно эту функцию взять за основу и для числа с N числом цифр. Тогда вопрос к IK - как будет выглядеть такая функция, если в качестве второго параметра передавать количество цифр в числе?

Можно сформулировать задачу еще более широко, если добавить в качестве третьего параметра основание системы счисления - десятичная, 16-ричная, 33-ричная и т.п.
Ratings: 0 negative/0 positive

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

Сообщений: 2543
Откуда: Рига
Дата: 06.07.16 09:31:34ОтветитьЦитировать
Игорь, я когда называл фукцию hash, просто придумал неудачное название, я как раз и имел в виду, что она должна выдавать разные значания для разных наборов цифр. Проверять как-то не было времени, поэтому и написал: "Как идея". Твоя функция вполне вместо нее подойдет. Можно еще загнать все цифры в массив, применить функцию ASORT, а потом загнать их обратно в строку.
Ratings: 0 negative/0 positive

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

Сообщений: 1960
Дата: 06.07.16 10:39:10ОтветитьЦитировать
Из условия не понятно, должны ли считаться числа 12000000 и 12222210 одинаковыми? Состоят ведь из одинаковых цифр. Вышеприведенные алгоритмы их различают.
Вот еще вариант решения "в лоб" для случая, если числа должны считаться одинаковыми (легко допилить и для другого случая, но по скорости вряд ли это самый оптимальный вариант):

  
  Create Cursor curTest (f1 c(8), f2 c(10))  
  For i =  1 To 100000  
  	Insert Into curTest Values (Padl(Int(Rand()*100000000), 8 ,"0"),"")  
  Endfor  
    
  Scan  
  	Replace f2 With dig(f1)  
  Endscan  
    
  Select * from curTest order by f2  
    
  Function dig  
  Lparameters cValue  
  cResult="**********"  
  For j = 1 To 8  
  	cDigit=Substr(cValue,j,1)  
  	cResult = Stuff(cResult,Val(cDigit)+1,1,cDigit)  
  Endfor  
  Return cResult
Ratings: 0 negative/0 positive

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

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 06.07.16 12:26:54ОтветитьЦитировать
ry
Из условия не понятно, должны ли считаться числа 12000000 и 12222210 одинаковыми?

Эти числа неодинаковые, у них разный состав - т.е. количество "1", "2", "0". Ну и пример приводил:

sphinx
(например, числа 12345, 54321, 13245, 13254, 32451 - относятся к одной группе, так как состав цифр, пусть и на разных позициях - одинаков).


Подобную функцию сортировки я писал, по сравнению с весовыми коэффициентами Игоря Королева - отработала в 5-6 раз медленнее. Полагаю, что и приседания типа "строка-массив-ASORT()-строка" не отработает быстрее.


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)




Исправлено: sphinx, 06.07.16 12:27
Ratings: 0 negative/0 positive

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

Сообщений: 31997
Дата: 06.07.16 13:10:24ОтветитьЦитировать
Simple777
Как я понимаю, можно эту функцию взять за основу и для числа с N числом цифр. Тогда вопрос к IK - как будет выглядеть такая функция, если в качестве второго параметра передавать количество цифр в числе?
От "разрядности" будет зависеть множитель. Если уж "упаковывать" по полной программе, то надо каждый OCCURS умножать на (K+1)^i где K число элементов ("цифр") в сочетании а i это индекс соответствующей "цифры" (от 0 до N-1)
Simple777
Можно сформулировать задачу еще более широко, если добавить в качестве третьего параметра основание системы счисления - десятичная, 16-ричная, 33-ричная и т.п.
Комбинаторика манипулирует элементами и множествами - там без разницы "цифры" в наборе или буквы или, скажем, разные виды домашних животных Для простоты, конечно, часто заменяют реальные сущности на числа (не цифры, а именно числа - от 0 до N-1 где N это общее число различных элементов).


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

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

Сообщений: 31997
Дата: 06.07.16 13:28:04ОтветитьЦитировать
Если важна скорость, и речь про фокс, то нужно прямо в запрос инлайнить эту здоровенную формулу. Хоть часть расходов (на вызов UDF) удастся сократить.


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

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

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 06.07.16 15:29:37ОтветитьЦитировать
Такая задача была на собеседовании, я ее вынужден был решать в Excel'е на VBA. Тогда написал в лоб, через сортировку, подозревал, что через весовые коэффициенты должна отработать быстрее, а это на больших объемах сказывается.


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

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

Сообщений: 19924
Дата: 06.07.16 16:01:25ОтветитьЦитировать
sphinx
Такая задача была на собеседовании

Чета у вас там в КУ совсем озверели, если на собеседовании дают такие задачи. Какой-то дебильный подход. :doom:

Я лишь однажды проходил нечто похожее на собеседование. Когда мне сказали, что берут "с испытательным сроком", я сказал тет-а-тет будущему непосредственному шефу, что испытательный срок взаимный. Главному боссу, канешна, я этого не говорил. В дальнейшем обе стороны прошли испытательный срок.

Вот ежели б я проводил собеседование... Что бы меня интересовало прежде всего? Много чего. Но главное - соотношение лояльности и компетентности у кандидата. Если баланс окажется неприемлемым, то никакие успешно пройденные тесты меня не переубедят. Общую же сообразительность надо проверять на достаточно нейтральных задачах. Если кандидат забыл/не знает некоторые команды/функции, то какое это может иметь значение? Да и нафига наизусть все помнить?

Вопчем, занимаются всякой херней работодатели.

Кстати. Если б работодатель у меня спросил бы: по какой причине я ушел с последнего места работы, я бы предложил "откровенность за откровенность" и попросил бы ответить на такой вопрос: А почему освободилось это место? Вопрос, кстати, абсолютно симметричный. [sm128]
Ratings: 0 negative/0 positive

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

Сообщений: 31997
Дата: 06.07.16 16:18:42ОтветитьЦитировать
offtop mode on

Лично я не вижу никакого "криминала" в подобном тестовом вопросе. Конечно, если дадут условия приемлемые для решения - и инструментальные средства и тот же доступ в интернет (я не обязан помнить все формулы из комбинаторики, да и "для дела" куда как полезнее "лентяй" за 5 минут находящий готовое решение проблемы в интернете, нежели "трудоголик" изобретающий каждый раз новый велосипед, ещё и с квадратными колёсами).
Задача вполне себе "нейтральная" - просто на общий уровень знаний (ну да, верхнее образование или самообразование тут нужно по любому - в школе этого не преподают ещё). Это не всучить тебе мега-проект на миллион строк исходника и попросить "предложить решения для ускорения вот этого бизнес-процесса"
И не тупое и безумно скушное "какие операторы цикла вы знаете" да "что такое SOLID" где умеющий складно бла-бла-бла и обладающий хорошей памятью но нулевым скиллом кодинга индивид влёгкую обходит реально понимающего в ремесле программирования чела

Впрочем, в экселе такого рода задачку решать - это уже нечто из разряда извращения

offtop mode off


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

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

Сообщений: 22329
Откуда: Каменск-Уральски
Дата: 06.07.16 16:26:33ОтветитьЦитировать
Simple777
Чета у вас там в КУ совсем озверели, если на собеседовании дают такие задачи. Какой-то дебильный подход.

Это в Екб, в КУ работу надо искать по блату, по крайней мере я давно плюнул на это - будет что-то случайное - рассмотрим.

Igor Korolyov
Лично я не вижу никакого "криминала" в подобном тестовом вопросе. Конечно, если дадут условия приемлемые для решения - и инструментальные средства и тот же доступ в интернет

Заданий было 5 штук - на все дали два дня дома. Тема на регулярные выражения - тоже была из той пачки, но я оставил свое свое решение, хотя и привел в описании решения код, который привел Игорь.

Да, задачи были такие, что за 5 минут я не знал, как их решать. Но.. интернет есть, время позволяет. Может и не сильно правильно/оптимально, но как сказал Игорь - проблема удачно решается.




------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

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

Сообщений: 5262
Дата: 12.07.16 05:52:22ОтветитьЦитировать
PaulWist
1+2+3+4+5 = 5+4+3+2+1 = 1+3+2+4+5 = 1+3+2+5+4 = 3+2+4+5+1
Не то,

Можно сравнивать суммы обратных чисел, а вместо 0 прибавлять 10. Т.е 12345670 = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 10. Возможно здесь и будут коллизии, но сходу контрпример мне придумать не удалось.
Ratings: 0 negative/0 positive

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

Сообщений: 2926
Откуда: Е-бург
Дата: 12.07.16 07:47:03ОтветитьЦитировать
spinz
PaulWist
1+2+3+4+5 = 5+4+3+2+1 = 1+3+2+4+5 = 1+3+2+5+4 = 3+2+4+5+1
Не то,

Можно сравнивать суммы обратных чисел, а вместо 0 прибавлять 10. Т.е 12345670 = 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 10. Возможно здесь и будут коллизии, но сходу контрпример мне придумать не удалось.
Как различить 2/6 и 1/3?
Ratings: 0 negative/0 positive

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

Сообщений: 5262
Дата: 12.07.16 07:52:50ОтветитьЦитировать
2/6 = 1/6 + 1/6. А какие другие две дроби с натуральным знаменателем не больше 9 дадут в сумме 1/3?

Т.е. может быть 1/9 + 1/9 + 1/9 = 1/3. Но тогда и к сумме 1/6 + 1/6 мы должны прибавить третью дробь.



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



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

On-line: 44 Дмитрий Петров  and Guests: 43


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