Создать все разделы подсписка

11

Учитывая непустой список целых чисел, выведите каждое возможное разбиение списка, где каждый раздел является непустым подсписком.

Итак, для списка [1, 2, 3, 4]результат:

[[1, 2, 3, 4]]
[[1, 2, 3], [4]]
[[1, 2], [3, 4]]
[[1, 2], [3], [4]]
[[1], [2, 3, 4]]
[[1], [2, 3], [4]]
[[1], [2], [3, 4]]
[[1], [2], [3], [4]]

Порядок списков в выходных данных не имеет значения, поэтому [[1, 2, 3, 4]]может быть первым, последним или где угодно. Порядок элементов должен быть сохранен.

Это код-гольф, поэтому выигрывает самый короткий ответ.

Связанный: Разделите список!

code-golf array-manipulation combinatorics set-partitions mbomb007
источник
2
Можем ли мы опустить окружение [...]в выходном формате? (До тех пор, пока разделы четко разделены, например, переводом строки.)
Мартин Эндер
Форматы ввода и вывода являются гибкими, но они должны быть похожими. Так что, если входной список имеет свои элементы в одной строке, выходные списки тоже должны.
mbomb007
Это не то, что я имею в виду. Посмотрите на ответ Bash. Он использует :в качестве разделителя списка, но в выходных данных сами разделы не включаются в дополнительную пару [...].
Мартин Эндер
Или по-другому: в вашем примере формата в задаче, я могу опустить первый [и последний ]из каждой строки?
Мартин Эндер
1
Тот же вопрос, что и советы
xnor

Ответы:

13

Сетчатка , 27 19 байт

Количество байтов предполагает кодировку ISO 8859-1.

+1%`,
;$'¶$`];[
;
,

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

объяснение

Конечно, это вычисляет все разделы, используя обработку строк. Основная идея заключается в том, что мы можем генерировать все разделы, решая для каждого ,индивидуально, хотим ли мы разделить список там. Такого рода вещи могут быть сделаны в Retina путем сопоставления каждого ,по очереди и использования замены, которая дает оба возможных выхода.

Входные данные действуют как базовый вариант: раздел, где все элементы все еще находятся в одном списке.

+1%`,
;$'¶$`];[

Теперь мы повторно ( +) сопоставляем первую ( 1) запятую ( ,) в каждой строке ( %) (обрабатывая эту строку как отдельную строку, которая важна для$' `` $ 1 `в подстановке).

Эта запятая заменяется на:

;   A semicolon. This is just a stand-in for the comma, so we know we've already
    processed it and it won't be substituted again by the next iteration.
$'  Everything after the match. This completes the first (unchanged) version of
    the current line.
¶   A linefeed. Since the next iteration will scan for all lines again, this doubles
    the number of strings we're working with.
$`  Everything before the match. This completes the second (split) version of
    the current line.
];[ A semicolon around which we split the list.

Помните, что все, что находится перед совпадением и после совпадения, остается в строке в любом случае, поэтому на самом деле полный результат $`;$'¶$`];[$'объясняет, почему мы вставляем суффикс и префикс в таком порядке.

Этот цикл останавливается, когда все запятые исчезают.

;
,

Наконец, замените точку с запятой снова запятой, чтобы соответствовать формату ввода.

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

Чистый Баш, 28

eval echo [${1//:/{:,]:[\}}]

Здесь списки разделены двоеточиями и заключены в квадратные скобки. Например, в вопросе список ввода будет иметь следующий вид 1:2:3:4:

[1:2:3:4] [1:2:3]:[4] [1:2]:[3:4] [1:2]:[3]:[4] [1]:[2:3:4] [1]:[2:3]:[4] [1]:[2]:[3:4] [1]:[2]:[3]:[4]

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

  • ${1//:/REPLACEMENT}заменяет двоеточие в $1с{:,]:[\}
  • Это создает расширение скобки, как [1{:,]:[}2{:,]:[}3{:,]:[}4]
  • Eval (и осторожные \побеги) приводит к тому, что расширение фигурной скобки происходит последним и дает желаемый результат.

Если необходимо точно соответствовать данному [[ , , ...]]формату, тогда мы можем сделать это вместо этого:

Чистый Баш, 47

eval printf '%s\\n' ${1//, /{\\,\\ ,]\\,\\ [\}}

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

Цифровая травма
источник
6

Pyth , 2 байта

./

С вводом [1, 2, 3, 4](например).

Пояснение : ./это оператор раздела. Он возвращает все деления входного списка в непересекающиеся подсписки. Ввод неявно подается в программу.

Проверьте это онлайн!

Джим
источник
6

05AB1E , 5 байтов

Œæʒ˜Q

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

Œæʒ˜Q  Main link. Argument l
Π     Get all sublists of l
 æ     Powerset of those lists
  ʒ˜Q  Filter: Keep the lists that when flattened equal the input
kalsowerus
источник
1
Вау, это очень аккуратный ответ!
Аднан
1
@ Adnan спасибо, я тоже очень доволен. Хотя это все, но эффективно :)
kalsowerus
Хороший ответ, когда еще не было встроенного, +1 от меня! Просто оставьте это для всех, кто придет сюда в будущем, но у 05AB1E теперь есть встроенная 2-байтовая функция для получения всех разделов .œ: Попробуйте онлайн.
Кевин Круйссен
4

Python 3 , 82 72 66 байт

f=lambda l:[k+[l[i:]]for i in range(len(l))for k in f(l[:i])]or[l]

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

-5 байт благодаря @JonathanAllan

овс
источник
О боже, я не могу ^ v снова :( Я действительно попробовал что-то подобное, и это не сработало, я, должно быть, где-то ошибся.
Джонатан Аллан
1
... в этом случае отбросьте еще 5
Джонатан Аллан
1
@JonathanAllan большое спасибо! Я мог бы сохранить другой байт за счет повторного использования lв конце концов
овс
Это решение уже существует здесь . Я отправил @feersum в TNB после публикации вопроса, чтобы у него была возможность опубликовать его.
mbomb007
Я не имел в виду, что вы должны отменить это, я просто имел в виду, что вы победили его в этом. Это твой выбор, конечно.
mbomb007
4

Haskell , 59 55 49 байт

p[x]=[[[x]]]
p(x:r)=do a:b<-p r;[(x:a):b,[x]:a:b]

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

Рекурсивное решение. Пример использования: p [1,2,3]возвращает [[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]].

-6 байт благодаря xnor !

Laikoni
источник
1
Вы можете написать вторую строку короче с помощью нотации do: do a:b<-p r;[(x:a):b,[x]:a:b](это меняет порядок списков).
xnor
1
Кроме того, <*>делает именно то, что вы хотите [\(a:b)->(x:a):b,([x]:)]<*>p r, хотя это дольше, чем doпотому, что первая лямбда, кажется, нуждается в сопоставлении с образцом.
xnor
3

J , 42 байта

<@(</."1)~<:@#_&(][:;<@(,~"{~0 1+>./)"1)0:

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

Например, вот процесс создания ключей для списка длиной 4.

пример

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

миль
источник
2

Брахилог , 2 байта

~c

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

Представление функции, которая производит вывод, действуя как генератор. (Ссылка TIO содержит дополнительный код для превращения его в полноценную программу для целей тестирования.)

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

объяснение

~c
~     Find a value with the following properties:
 c      concatenating its elements produces {the input}

источник
2

APL, 26 байт

{⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵}

Тест:

      {⊂∘⍵¨1,¨↓⍉(X⍴2)⊤⍳2*X←⍴1↓⍵} 1 2 3 4
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│┌─────┬─┐│┌───┬───┐│┌───┬─┬─┐│┌─┬─────┐│┌─┬───┬─┐│┌─┬─┬───┐│┌─┬─┬─┬─┐│┌───────┐│
││1 2 3│4│││1 2│3 4│││1 2│3│4│││1│2 3 4│││1│2 3│4│││1│2│3 4│││1│2│3│4│││1 2 3 4││
│└─────┴─┘│└───┴───┘│└───┴─┴─┘│└─┴─────┘│└─┴───┴─┘│└─┴─┴───┘│└─┴─┴─┴─┘│└───────┘│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

Объяснение:

  • X←⍴1↓⍵: Xдлина ⍵(входного списка) с первым пропущенным элементом
  • ⍳2*X: числа [1..2 ^ X]
  • (X⍴2)⊤: base-2 представление этих чисел, с Xпозициями (то есть, Xсамо будет переходить в 0).
  • ↓⍉: повернуть матрицу и разделить ее по линиям (⊤ в результате получим матрицу с числами вдоль столбцов), получив массив битовых векторов
  • 1,¨: добавьте 1 к каждому битовому вектору.
  • ⊂∘⍵¨: для каждого битового вектора, разделить ⍵на каждый 1.
Мэринус
источник
1

питон , 90 байт

переиграл овцами (делая что-то, что я думал, что попробовал работать: p)

def f(a):r=[[a]];i=len(a)-1;exec("for s in f(a[:i]):s+=[a[i:]];r+=[s]\ni-=1\n"*i);return r

Рекурсивная функция, которая создает список разделов из срезов ввода с хвостом, достигнутым, когда срезы имеют длину 1.

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

execСохраняет 4 байта в течение whileили 3 в течение forцикла (ниже) , так как это означает , что только два \nсек , а не два уровня отступа, позволяя все функции , чтобы находиться на одной линии ( в то время как порядок нарезки не имеет значения).

def f(a):
 r=[[a]]
 for i in range(1,len(a)):
  for s in f(a[:i]):s+=[a[i:]];r+=[s]
 return r
Джонатан Аллан
источник
1

Haskell, 59 байт

x#[]=[[[x]]]
x#(a:b)=[(x:a):b,[x]:a:b]
foldr((=<<).(#))[[]]
alephalpha
источник
1

Рубин , 62 57 байт

->l{(0..2**l.size).map{|x|l.chunk{1&x/=2}.map &:last}|[]}

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

Как это работает:

  • Количество разделов равно 2 ^ (n-1): я перебираю двоичные числа в этом диапазоне, беру группы нулей и единиц и отображаю их как подмножества исходного списка.
  • Вместо того, чтобы возиться с диапазоном, я делаю его двойным и в конце отбрасываю дубликаты. Теперь я также могу отбросить первую двоичную цифру и сделать функцию чанка короче.
гигабайт
источник
0

JavaScript (ES6), 87 байт

([e,...a],b=[],c=[e],d=[...b,c])=>1/a[0]?[...f(a,b,[...c,a[0]]),...f(a,d,[a[0]])]:[d]

Объяснение: bэто список предыдущих подсписков, cэто текущий подсписок (который начинается как первый элемент массива, поскольку он должен быть в первом подсписке), а dсписок всех подсписков. Остальные элементы массива затем рекурсивно обрабатываются. В каждом случае есть две опции: либо следующий элемент добавляется к текущему подсписку, либо текущий подсписок завершается, а следующий элемент запускает новый подсписок. Затем рекурсивные результаты объединяются вместе. Когда массив исчерпан, список списка всех подсписков является результатом.

Нил
источник
0

APL (NARS) 38 символов, 76 байтов

{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

здесь используется функция Nars 11 1‼ kk, но она очень медленная, ее уже нельзя использовать для массива arg из 9 элементов ... 

  P3←{k←↑⍴⍵⋄x←11 1‼k k⋄y←⍵⋄∪{x[⍵;]⊂y}¨⍳↑⍴x}

  ⍴∘P3¨{1..⍵}¨⍳8
1  2  4  8  16  32  64  128 
  P3 'abcd'
abcd    abc d    ab cd    a bcd    ab c d    a bc d    a b cd    a b c d

ниже приведена функция, которая не использует встроенную функцию:

r←h w;k;i
   r←⊂,⊂w⋄k←↑⍴w⋄i←1⋄→B
A: r←r,(⊂⊂,i↑w),¨h i↓w⋄i+←1
B: →A×⍳i<k

  h 'abcd'
abcd    a bcd    a b cd    a b c d    a bc d    ab cd    ab c d    abc d
  ⍴∘h¨{1..⍵}¨⍳8
2  4  8  16  32  64  128

мы выбираем тип каждого результата:

  o h ,1
┌──────┐
│┌1───┐│
││┌1─┐││
│││ 1│││
││└~─┘2│
│└∊───┘3
└∊─────┘
  o h 1 2
┌2───────────────────┐
│┌1─────┐ ┌2────────┐│
││┌2───┐│ │┌1─┐ ┌1─┐││
│││ 1 2││ ││ 1│ │ 2│││
││└~───┘2 │└~─┘ └~─┘2│
│└∊─────┘ └∊────────┘3
└∊───────────────────┘

Я не знаю, как это работает, это всего лишь эвристическая попытка ...

Возможно я сделаю какую-то ошибку; обе функции строят разделы списка независимо от ввода, а не только 1 2 ... n.

RosLuP
источник
0

Аксиома, 251 байт

C==>concat;A==>List Any;px(a:A):A==(k:=#a;r:=copy[a];k<=1=>r;i:=1;repeat(i>=k=>break;x:=a.(1..i);y:=a.((i+1)..k);z:=px(y);t:=[x,z.1];for j in 2..#z repeat(w:=(z.j)::A;m:=#w;v:=[x];for q in 1..m repeat v:=C(v,w.q);t:=C(t,[v]));r:=C(r,copy t);i:=i+1);r)

Если кто-то найдет что-то лучше ... ungof и проверить

pp(a:List Any):List Any==
  k:=#a;r:=copy[a];k<=1=>r;i:=1
  repeat
    i>=k=>break
    x:=a.(1..i);y:=a.((i+1)..k);z:=pp(y);
    t:=[x,z.1]
    for j in 2..#z repeat
           w:=(z.j)::List Any
           m:=#w; v:=[x]
           for q in 1..m repeat 
                       v:=concat(v,w.q);
           t:=concat(t,[v])
    r:=concat(r,copy t);
    i:=i+1
  r

(7) -> px []
 (7)  [[]]
                                                           Type: List Any
(8) -> px [1]
 (8)  [[1]]
                                                           Type: List Any
(9) -> px [1,2]
 (9)  [[1,2],[[1],[2]]]
                                                           Type: List Any
(10) -> px [1,2,3]
 (10)  [[1,2,3],[[1],[2,3]],[[1],[2],[3]],[[1,2],[3]]]
                                                           Type: List Any
(11) -> px [1,2,3,4,5,6]
 (11)
[[1,2,3,4,5,6], [[1],[2,3,4,5,6]], [[1],[2],[3,4,5,6]],
 [[1],[2],[3],[4,5,6]], [[1],[2],[3],[4],[5,6]], [[1],[2],[3],[4],[5],[6]],
 [[1],[2],[3],[4,5],[6]], [[1],[2],[3,4],[5,6]], [[1],[2],[3,4],[5],[6]],
 [[1],[2],[3,4,5],[6]], [[1],[2,3],[4,5,6]], [[1],[2,3],[4],[5,6]],
 [[1],[2,3],[4],[5],[6]], [[1],[2,3],[4,5],[6]], [[1],[2,3,4],[5,6]],
 [[1],[2,3,4],[5],[6]], [[1],[2,3,4,5],[6]], [[1,2],[3,4,5,6]],
 [[1,2],[3],[4,5,6]], [[1,2],[3],[4],[5,6]], [[1,2],[3],[4],[5],[6]],
 [[1,2],[3],[4,5],[6]], [[1,2],[3,4],[5,6]], [[1,2],[3,4],[5],[6]],
 [[1,2],[3,4,5],[6]], [[1,2,3],[4,5,6]], [[1,2,3],[4],[5,6]],
 [[1,2,3],[4],[5],[6]], [[1,2,3],[4,5],[6]], [[1,2,3,4],[5,6]],
 [[1,2,3,4],[5],[6]], [[1,2,3,4,5],[6]]]
                                                           Type: List Any
(12) -> [[i,#px i] for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (12)
[[[],1],[[1],1],[[1,2],2],[[1,2,3],4],[[1,2,3,4],8],[[1,2,3,4,5,6],32]]
                                                      Type: List List Any
(13) -> [#px(i) for i in [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5,6]] ]
 (13)  [1,1,2,4,8,32]
                                            Type: List NonNegativeInteger

Если это слишком много места, скажите это, и я уберу примеры ...

RosLuP
источник