Biorąc pod uwagę niepustą listę liczb całkowitych, wypisz wszystkie możliwe partycjonowanie listy, gdzie każda partycja jest niepustą listą podrzędną.

Tak więc dla listy [1, 2, 3, 4]wynik jest następujący:

[[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]]

Kolejność list w danych wyjściowych nie ma znaczenia, więc [[1, 2, 3, 4]]może być pierwsza, ostatnia lub gdziekolwiek. Kolejność elementów musi zostać zachowana.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź.

Powiązane: Podziel listę na części!

Galaretka , 2 bajty

ŒṖ

Wypróbuj online!

Retina , 27 19 bajtów

Liczba bajtów zakłada kodowanie ISO 8859-1.

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

Wypróbuj online!

Wyjaśnienie

Oczywiście oblicza to wszystkie partycje przy użyciu przetwarzania ciągów. Podstawową ideą jest to, że możemy wygenerować wszystkie partycje, decydując o każdej z nich, indywidualnie czy chcemy tam podzielić listę. Tego rodzaju rzeczy można wykonać w siatkówce, dopasowując ,kolejno i używając zamiennika, który daje oba możliwe wyniki.

Dane wejściowe działają jak przypadek podstawowy: partycja, w której wszystkie elementy wciąż znajdują się na jednej liście.

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

Teraz wielokrotnie ( +) dopasowujemy pierwszy ( 1) przecinek ( ,) w każdym wierszu (% ) (traktując ten wiersz jako osobny ciąg, który jest istotny $'i `` 1 $ '' w podstawieniu).

Ten przecinek zostanie zastąpiony przez:

;   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.

Pamiętaj, że wszystko przed meczem i po meczu i tak pozostaje w ciągu, więc pełny wynik jest w rzeczywistości $`;$'¶$`];[$' wyjaśnia, dlaczego wstawiamy sufiks i prefiks w tej kolejności.

Ta pętla zatrzymuje się, gdy znikną wszystkie przecinki.

;
,

Na koniec zamień średniki ponownie przecinkami, aby dopasować format wejściowy.

Pure Bash, 28

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

Tutaj listy są oddzielone dwukropkiem i zawarte w nawiasach kwadratowych. Na przykład w pytaniu będzie lista wejściowa, 1:2:3:4a wynikiem będzie:

[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]

Wypróbuj online .

• ${1//:/REPLACEMENT}zastępuje dwukropek w $1z{:,]:[\}
• Generuje to rozwinięcie nawiasów jak [1{:,]:[}2{:,]:[}3{:,]:[}4]
• Eval (i ostrożne \ucieczki) powoduje, że rozszerzenie nawiasu następuje na końcu i daje pożądany rezultat.

Jeśli konieczne jest dokładne dopasowanie do podanego [[ , , ...]] formatu, możemy to zrobić w zamian:

Pure Bash, 47

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

Wypróbuj online .

Pyth , 2 bajty

./

Z wejściem [1, 2, 3, 4](na przykład).

Objaśnienie : ./jest operatorem partycji. Zwraca wszystkie podziały listy wejściowej na rozłączne podlisty. Dane wejściowe są domyślnie podawane do programu.

Przetestuj online!

05AB1E , 5 bajtów

Œæʒ˜Q

Wypróbuj online!

Œæʒ˜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

Python 3 , 82 72 66 bajtów

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

Wypróbuj online!

-5 bajtów dzięki @JonathanAllan

Haskell , 59 55 49 bajtów

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

Wypróbuj online!

Rozwiązanie rekurencyjne. Przykład użycia: p [1,2,3]zwraca [[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]].

-6 bajtów dzięki xnor !

J , 42 bajty

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

Generuje wszystkie partycje podlisty, tworząc klucze do podlist listy partycji o długości 1 i iterując do długości listy danych wejściowych. Każda podlista partycji jest następnie tworzona przez wybranie z kluczy.

Na przykład tutaj jest proces tworzenia kluczy dla listy o długości 4.

Wypróbuj online!

J , 26 24 bajtów

<@(<;.1)~2#:@(+i.)@^<:@#

Wypróbuj online!

Brachylog , 2 bajty

~c

Wypróbuj online!

Podanie funkcji, które wytwarza dane wyjściowe poprzez działanie jako generator. (Łącze TIO zawiera dodatkowy kod, aby przekształcić go w pełny program do celów testowych.)

Nawiasem mówiąc, chociaż nie jest to technicznie wbudowane, jest to tak powszechnie używane w Brachylog, że a) prawdopodobnie zasługuje na reprezentację jednobajtową, i b) cwbudowane może przyjąć parametr, aby wprowadzić twierdzenia na temat swoich danych wejściowych (podczas gdy w przypadku większości wbudowanych parametr mówi o tym, jak wytworzyć wynik ).

Wyjaśnienie

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

APL, 26 bajtów

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

Test:

      {⊂∘⍵¨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││
│└─────┴─┘│└───┴───┘│└───┴─┴─┘│└─┴─────┘│└─┴───┴─┘│└─┴─┴───┘│└─┴─┴─┴─┘│└───────┘│
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

Wyjaśnienie:

• X←⍴1↓⍵: Xjest długością ⍵(listy wejściowej) z pominiętym pierwszym elementem
• ⍳2*X: liczby [1..2 ^ X]
• (X⍴2)⊤: reprezentacja tych liczb przez base-2 z Xpozycjami (tzn. Xsama się zawinie 0).
• ↓⍉: obróć matrycę i podziel ją wzdłuż linii (⊤ daje w wyniku macierz z liczbami wzdłuż kolumn), dając tablicę wektorów bitowych
• 1,¨: wstaw 1 do każdego wektora bitowego.
• ⊂∘⍵¨: dla każdego wektora bitowego, podzielone ⍵dla każdego 1.

Haskell , 45 bajtów

foldr(\h t->map([h]:)t++[(h:y):z|y:z<-t])[[]]

Wypróbuj online!

Znalazłem to rozwiązanie jakiś czas temu, myśląc o końcówce Haskell .

Pyton , 90 bajtów

outgolfed by ovs (robiąc coś, o czym myślałem, że próbowałem pracować: 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

Funkcja rekurencyjna, która tworzy listę partycji z wycinków wejścia z ogonem osiągniętym, gdy wycinki mają długość 1.

Wypróbuj online!

execZapisuje 4 bajty ponad whilelub 3 na forpętli (poniżej), ponieważ oznacza to, że tylko dwa \ns, zamiast dwóch poziomów wcięć, dzięki czemu cała funkcja się na jednej linii (przy celu krojenia nie ma znaczenia).

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

Python 3 , 67 bajtów

f=lambda x,n=1:x[n:]and[y+[x[n:]]for y in f(x[:n])]+f(x,n+1)or[[x]]

Wypróbuj online!

Haskell, 59 bajtów

x#[]=[[[x]]]
x#(a:b)=[(x:a):b,[x]:a:b]
foldr((=<<).(#))[[]]

Rubin , 62 57 bajtów

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

Wypróbuj online!

Jak to działa:

• Liczba partycji wynosi 2 ^ (n-1): Ieruję liczby binarne w tym zakresie, biorę grupy zer i jedynek i mapuję je jako podzbiory początkowej listy.
• Zamiast majstrować przy zasięgu, podwajam go i na końcu odrzucam duplikaty. Teraz mogę też odrzucić pierwszą cyfrę binarną i skrócić funkcję porcji.

JavaScript (ES6), 87 bajtów

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

Objaśnienie: bjest listą poprzednich podlist, cjest bieżącą podlistą (która zaczyna się jako pierwszy element tablicy, ponieważ musi znajdować się w pierwszej podlistie), podczas gdy djest listą wszystkich podlist. Reszta elementów tablicy jest następnie rekurencyjnie przetwarzana. W każdym przypadku istnieją dwie opcje: albo następny element zostanie dołączony do bieżącej listy podrzędnej, albo bieżąca lista podrzędna zostanie ukończona, a następny element rozpocznie nową podlistę. Wyniki rekurencyjne są następnie łączone razem. Gdy tablica jest wyczerpana, wynikiem jest lista wszystkich podlist.

APL (NARS) 38 znaków, 76 bajtów

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

to używa funkcji Nars 11 1‼ kk, ale jest bardzo wolne, nie nadaje się do tablicy 9 elementów już ...

  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

poniżej znajduje się funkcja, która nie korzysta z wbudowanego:

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 

widzimy typ każdego wyniku:

  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
└∊───────────────────┘

Nie wiem jak to działa, to tylko heurystyczna próba ...

Możliwe Popełniam błąd; obie funkcje budują partycje listy bez względu na dane wejściowe i nie tylko 1 2 ... n.

Aksjomat, 251 bajtów

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)

Jeśli ktoś znajdzie coś lepszego ... Ungof i przetestuj:

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

Jeśli to za dużo miejsca, powiedz to i usuwam przykłady ...