Найти подмножества факторов

14

Давайте представим, что у нас есть конечный набор натуральных чисел. Этот набор может быть представлен как линия точек, где каждое целое число, присутствующее в наборе, заполняется как скантрон или перфокарта . Например, набор {1,3,4,6}может быть представлен как:

*.**.*

*представляет член нашего набора и .представляет целое число, которое не является членом множества.

Эти наборы имеют «факторы». Свободно х является фактором у, если у можно построить из копий х. Более строгое наше определение фактора заключается в следующем:

  • x является фактором y тогда и только тогда, когда y является объединением нескольких непересекающихся множеств, все из которых являются x со смещением.

Мы могли бы назвать *.*в фактор из , *.**.*потому что это совершенно ясно из двух экземпляров *.*пут конца в конец.

*.**.*
------
*.*...
...*.*

Факторы не должны быть сквозными, мы также сказали бы, что *.*это фактор*.*.*.*

*.*.*.*
-------
*.*....
....*.*

Факторы также могут пересекаться. Это означает *.*также фактор****

****
----
*.*.
.*.*

Однако число не может быть охвачено фактором более одного раза. Например *.*, не является фактором *.*.*.


Вот более сложный пример:

 *..*.**..***.*.*

Это имеет *..*.*как фактор. Вы можете увидеть это ниже, где я выстроил три экземпляра *..*.*.

*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*

задача

Учитывая набор любым разумным представлением, выведите все наборы, которые являются факторами ввода.

Вы можете индексировать по любому значению (то есть вы можете выбрать наименьшее число, которое может присутствовать во входных данных). Вы также можете предположить, что входной набор всегда будет содержать это наименьшее значение.

Это вопрос поэтому вы должны стремиться сделать это как можно меньше байтов.

Тестовые случаи

Эти тесты были сделаны вручную, может быть ошибка или два на более крупных

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
Пост Рок Гарф Хантер
источник
Если мы возьмем набор в виде списка чисел (например, [1,3,5,7]для *.*.*.*), можем ли мы предположить, что он отсортирован?
Мартин Эндер
1
Это эквивалентно нахождению делителей многочленов, коэффициенты которых ограничены 0 и 1?
xnor
1
@xnor Я не уверен. Если *.*.*= x+x^2+x^4, то 1+x+x^2= ***будет делителем, верно? x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
mbomb007
1
@JonathanAllan Для ваших примеров *указан как фактор, представляющий то же подмножество, что *.и *...
Мартин Эндер
1
@JonathanAllan В нем говорится, выводить все наборы, а не выводить все представления ASCII действительных наборов.
Мартин Эндер

Ответы:

3

Mathematica, 71 68 байт

#&@@@Cases[(s=Subsets)@s@#,x_/;Sort[Join@@x]==#&&Equal@@(#&@@@x-x)]&

Введите как {1,3,5,7}(отсортировано) и как {{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. Функция выдаст кучу сообщений.

Это O (2 2 Нет ) (где N - длина входа и o = p = e = 1 ...). Он генерирует все подмножества подмножеств, затем выбирает те, которые приводят к отправке ввода при объединении (при условии, что мы рассматриваем только разделы) и где все элементы одинаковы, если мы вычитаем наименьшее значение каждого подмножества).

Мартин Эндер
источник
2

Желе , 12 байт

;÷@DỊȦ
ÆDçÐf

Ввод и вывод используют 1и 0вместо *и ..

Попробуйте онлайн!

Как это устроено

ÆDçÐf   Main link. Argument: n (integer with decimal digits 1 and 0)

ÆD      Compute all divisors of n.
  çÐf   Filter; call the helper link with left argument d and right argument n for
        all divisors d of n. Return the array of d's for which the helper link
        returns a truthy value.


;÷@DỊȦ  Helper link. Left argument: d. Right argument: n

 ÷@     Divide n by d.
;       Concatenate, yielding [d, n÷d].
   D    Decimal; convert both integers in the pair to base 10.
    Ị   Insignificant; map 1 and 0 to 1, all other positive integers to 0.
     Ȧ  All; return 1 iff the result contains no zeroes.
Деннис
источник