Давайте представим, что у нас есть конечный набор натуральных чисел. Этот набор может быть представлен как линия точек, где каждое целое число, присутствующее в наборе, заполняется как скантрон или перфокарта . Например, набор {1,3,4,6}может быть представлен как:
*.**.*
*представляет член нашего набора и .представляет целое число, которое не является членом множества.
Эти наборы имеют «факторы». Свободно х является фактором у, если у можно построить из копий х. Более строгое наше определение фактора заключается в следующем:
- x является фактором y тогда и только тогда, когда y является объединением нескольких непересекающихся множеств, все из которых являются x со смещением.
Мы могли бы назвать *.*в фактор из , *.**.*потому что это совершенно ясно из двух экземпляров *.*пут конца в конец.
*.**.*
------
*.*...
...*.*
Факторы не должны быть сквозными, мы также сказали бы, что *.*это фактор*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Факторы также могут пересекаться. Это означает *.*также фактор****
****
----
*.*.
.*.*
Однако число не может быть охвачено фактором более одного раза. Например *.*, не является фактором *.*.*.
Вот более сложный пример:
*..*.**..***.*.*
Это имеет *..*.*как фактор. Вы можете увидеть это ниже, где я выстроил три экземпляра *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
задача
Учитывая набор любым разумным представлением, выведите все наборы, которые являются факторами ввода.
Вы можете индексировать по любому значению (то есть вы можете выбрать наименьшее число, которое может присутствовать во входных данных). Вы также можете предположить, что входной набор всегда будет содержать это наименьшее значение.
Это вопрос кода-гольфа, поэтому вы должны стремиться сделать это как можно меньше байтов.
Тестовые случаи
Эти тесты были сделаны вручную, может быть ошибка или два на более крупных
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
источник
[1,3,5,7]для*.*.*.*), можем ли мы предположить, что он отсортирован?*.*.*=x+x^2+x^4, то1+x+x^2=***будет делителем, верно?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*указан как фактор, представляющий то же подмножество, что*.и*...Ответы:
Mathematica,
7168 байтВведите как
{1,3,5,7}(отсортировано) и как{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. Функция выдаст кучу сообщений.Это O (2 2 Нет ) (где N - длина входа и o = p = e = 1 ...). Он генерирует все подмножества подмножеств, затем выбирает те, которые приводят к отправке ввода при объединении (при условии, что мы рассматриваем только разделы) и где все элементы одинаковы, если мы вычитаем наименьшее значение каждого подмножества).
источник
Желе , 12 байт
Ввод и вывод используют
1и0вместо*и..Попробуйте онлайн!
Как это устроено
источник