11

Diberikan daftar bilangan bulat kosong, hasilkan setiap kemungkinan partisi dari daftar di mana setiap partisi adalah sublist kosong.

Jadi untuk daftar [1, 2, 3, 4]hasilnya adalah:

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

Urutan daftar dalam output tidak masalah, jadi [[1, 2, 3, 4]]bisa menjadi yang pertama, terakhir, atau di mana pun. Urutan elemen harus dilestarikan.

Ini kode-golf, jadi jawaban tersingkat menang.

Terkait: Partisi daftar!

code-golf array-manipulation combinatorics set-partitions mbomb007
sumber

2

Bisakah kita menghilangkan sekitarnya [...]dalam format output? (Selama partisi jelas dipisahkan, misalnya dengan linefeeds.)

Martin Ender

Format input dan output fleksibel, tetapi formatnya harus sama. Jadi, jika daftar input memiliki unsur-unsurnya pada satu baris, daftar keluaran juga harus.

mbomb007

Bukan itu yang saya maksud. Lihatlah jawaban Bash. Ini digunakan :sebagai pemisah daftar tetapi dalam output, partisi itu sendiri tidak dibungkus dengan pasangan tambahan [...].

Martin Ender

Atau, ditanyakan berbeda: dalam format contoh Anda dalam tantangan, dapatkah saya melepaskan baris pertama [dan terakhir ]dari setiap baris?

Martin Ender

1

Pertanyaan yang sama dengan tips

xnor

2

Jelly , 2 byte

ŒṖ

Cobalah online!

Dennis
sumber

13

Retina , 27 19 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

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

Cobalah online!

Penjelasan

Tentu saja ini menghitung semua partisi menggunakan pemrosesan string. Ide dasarnya adalah bahwa kita dapat menghasilkan semua partisi dengan memutuskan untuk masing-masing secara ,terpisah apakah kita ingin membagi daftar di sana. Hal-hal semacam ini dapat dilakukan di Retina dengan mencocokkan masing-masing, secara bergantian dan menggunakan pengganti yang memberikan kemungkinan keluaran.

Input bertindak sebagai basis huruf: partisi di mana semua elemen masih dalam satu daftar.

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

Sekarang kami berulang kali ( +) cocok dengan 1koma pertama ( ,), pada setiap baris (% ) (memperlakukan baris itu sebagai string terpisah, yang relevan untuk $'dan `` $ 1 `dalam substitusi).

Koma itu akan diganti dengan:

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

Ingatlah bahwa semua yang ada di depan pertandingan dan setelah pertandingan tetap ada di dalam string, jadi hasil penuh sebenarnya $`;$'¶$`];[$' yang menjelaskan mengapa kita memasukkan akhiran dan awalan dalam urutan itu.

Loop ini berhenti setelah semua koma hilang.

;
,

Akhirnya, ganti koma dengan koma lagi untuk mencocokkan format input.

Martin Ender
sumber

10

Pure Bash, 28

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

Di sini, daftar dipisahkan dengan titik dua, dan terkandung dalam tanda kurung. Misalnya dalam pertanyaan, daftar input akan 1:2:3:4dan hasilnya adalah:

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

Cobalah online .

${1//:/REPLACEMENT}menggantikan titik dua $1dengan{:,]:[\}
Ini menghasilkan ekspansi penjepit seperti [1{:,]:[}2{:,]:[}3{:,]:[}4]
Eval (dan \lolos dengan hati-hati ) menyebabkan ekspansi brace terjadi terakhir dan memberikan hasil yang diinginkan.

Jika perlu untuk mencocokkan dengan [[ , , ...]]format yang diberikan , maka kita dapat melakukan ini sebagai gantinya:

Pure Bash, 47

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

Cobalah online .

Trauma Digital
sumber

6

Pyth , 2 byte

./

Dengan input [1, 2, 3, 4](misalnya).

Penjelasan : ./adalah operator partisi. Ini mengembalikan semua divisi dari daftar input menjadi sub-daftar terpisah. Masukan secara implisit dimasukkan ke program.

Uji secara online!

Jim
sumber

6

05AB1E , 5 byte

Œæʒ˜Q

Cobalah 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

kalsowerus
sumber

1

Wow, ini jawaban yang sangat rapi!

Adnan

1

@ Adnan terima kasih, saya juga cukup senang dengan itu. Meskipun semuanya tapi efisien :)

kalsowerus

Jawaban bagus ketika belum ada builtin, +1 dari saya! Hanya meninggalkan ini untuk orang lain yang datang ke sini di masa depan, tetapi 05AB1E sekarang memiliki built-in 2-byte untuk mendapatkan semua partisi .œ:: Cobalah online.

Kevin Cruijssen

4

Python 3 , 82 72 66 byte

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

Cobalah online!

-5 byte terima kasih kepada @JonathanAllan

ovs
sumber

Ya ampun, aku tidak bisa ^ v lagi :( Aku benar-benar mencoba sesuatu seperti ini dan itu tidak berhasil, aku pasti salah di suatu tempat.

Jonathan Allan

1

... dalam hal ini memotong 5 lebih

Jonathan Allan

1

@ Jonathan Allan, terima kasih banyak! Saya bisa menyimpan byte lain dengan menggunakan kembali lpada akhirnya

ov

Solusi ini sudah ada di sini . Saya mengirim pesan @feersum di TNB setelah memposting pertanyaan, sehingga ia memiliki kesempatan untuk mempostingnya.

mbomb007

Saya tidak bermaksud bahwa Anda harus membatalkannya, saya hanya bermaksud bahwa Anda mengalahkannya. Itu pilihan Anda, tentu saja.

mbomb007

4

Haskell , 59 55 49 byte

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

Cobalah online!

Solusi rekursif. Contoh penggunaan: p [1,2,3]pengembalian [[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]].

-6 byte terima kasih kepada xnor !

Laikoni
sumber

1

Anda dapat menulis baris kedua lebih pendek dengan notasi: do a:b<-p r;[(x:a):b,[x]:a:b](ini mengubah urutan daftar).

xnor

1

Juga, <*>lakukan persis apa yang Anda inginkan [\(a:b)->(x:a):b,([x]:)]<*>p r, meskipun itu lebih lama daripada dokarena lambda pertama tampaknya membutuhkan kecocokan pola.

xnor

3

J , 42 byte

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

Hasilkan semua sublist partiton dengan membuat tombol untuk sub-partisi partisi dengan panjang 1 dan iterasi ke panjang daftar input. Setiap sublist partisi kemudian dibentuk dengan memilih dari tombol.

Sebagai contoh, berikut adalah proses membuat kunci untuk daftar panjang 4.

Contoh

Cobalah online!

mil
sumber

3

J , 26 24 byte

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

Cobalah online!

mil
sumber

2

Brachylog , 2 byte

~c

Cobalah online!

Pengajuan fungsi yang menghasilkan output melalui bertindak sebagai generator. (TIO link berisi kode tambahan untuk menjadikan ini menjadi program lengkap, untuk tujuan pengujian.)

Secara kebetulan, meskipun secara teknis bukan builtin, ini sangat umum digunakan di Brachylog sehingga a) mungkin layak untuk representasi byte tunggal, dan b) cbuiltin dapat mengambil parameter untuk membuat pernyataan tentang inputnya (sedangkan dengan sebagian besar builtin, parameter berbicara tentang cara menghasilkan output ).

Penjelasan

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

sumber

2

APL, 26 byte

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

Uji:

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

Penjelasan:

X←⍴1↓⍵: Xadalah panjang ⍵(daftar input) dengan elemen pertama dijatuhkan
⍳2*X: angka [1..2 ^ X]
(X⍴2)⊤: basis-2 representasi angka-angka itu, dengan Xposisi (yaitu Xdirinya akan membungkus ke 0).
↓⍉: memutar matriks dan membaginya di sepanjang garis ( ⊤memberikan sebagai hasilnya matriks dengan angka di sepanjang kolom), memberikan array vektor bit
1,¨: tambahkan 1 untuk setiap bit vektor.
⊂∘⍵¨: untuk setiap vektor bit, bagi ⍵masing-masing 1.

marinus
sumber

2

Haskell , 45 byte

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

Cobalah online!

Saya menemukan solusi ini beberapa waktu lalu ketika memikirkan tentang tip Haskell .

Tidak
sumber

1

Python , 90 byte

kalah oleh ovs (membuat sesuatu yang saya pikir saya sudah mencoba bekerja: 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

Fungsi rekursif yang membangun daftar partisi dari irisan input dengan ekor tercapai ketika irisan memiliki panjang 1.

Cobalah online!

The execmenghemat 4 byte atas whileatau 3 di atas forlingkaran (bawah) karena itu berarti hanya dua \ns daripada dua tingkat lekukan, yang memungkinkan seluruh fungsi berada di satu baris (sementara urutan mengiris tidak masalah).

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

Jonathan Allan
sumber

1

Python 3 , 67 byte

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

Cobalah online!

Dennis
sumber

1

Haskell, 59 byte

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

alephalpha
sumber

1

Ruby , 62 57 byte

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

Cobalah online!

Bagaimana itu bekerja:

Jumlah partisi adalah 2 ^ (n-1): Saya beralih pada bilangan biner dalam rentang itu, ambil kelompok nol dan satu dan memetakannya sebagai himpunan bagian dari daftar awal.
Alih-alih mengutak-atik kisaran, saya membuatnya ganda dan membuang duplikat di akhir. Sekarang saya juga bisa membuang digit biner pertama dan membuat fungsi chunk lebih pendek.

GB
sumber

0

JavaScript (ES6), 87 byte

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

Penjelasan: badalah daftar csublist sebelumnya, adalah sublist saat ini, (yang dimulai sebagai elemen pertama dari array, karena itu harus ada dalam sublist pertama) sementara itu dadalah daftar semua sub daftar. Sisa elemen array kemudian diproses secara rekursif. Dalam setiap kasus ada dua opsi: elemen berikutnya ditambahkan ke sublist saat ini, atau sublist saat ini selesai dan elemen berikutnya memulai sublist baru. Hasil rekursif kemudian digabungkan bersama. Ketika array habis, daftar daftar semua sublists adalah hasilnya.

Neil
sumber

0

APL (NARS) 38 char, 76 byte

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

ini menggunakan fungsi Nars 11 1‼ kk tetapi sangat lambat, tidak dapat digunakan untuk array arg dari 9 elemen ...

  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

di bawah ini adalah fungsi yang tidak menggunakan bawaan:

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

kami melihat jenis setiap hasil:

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

Saya tidak tahu cara kerjanya, itu hanya coba heuristik ...

Mungkin saya membuat kesalahan; kedua fungsi membangun partisi dari daftar input apa pun dan tidak hanya 1 2 ... n.

RosLuP
sumber

0

Aksioma, 251 byte

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)

Jika seseorang menemukan sesuatu yang lebih baik ... ungof dan uji:

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

Jika ini terlalu banyak ruang mengatakan itu dan saya menghapus contoh ...

RosLuP
sumber

Hasilkan semua Partisi Partisi

Jawaban:

Jelly , 2 byte

Retina , 27 19 byte

Penjelasan

Pure Bash, 28

Pure Bash, 47

Pyth , 2 byte

05AB1E , 5 byte

Python 3 , 82 72 66 byte

Haskell , 59 55 49 byte

J , 42 byte

J , 26 24 byte

Brachylog , 2 byte

Penjelasan

APL, 26 byte

Haskell , 45 byte

Python , 90 byte

Python 3 , 67 byte

Haskell, 59 byte

Ruby , 62 57 byte

Bagaimana itu bekerja:

JavaScript (ES6), 87 byte

APL (NARS) 38 char, 76 byte

Aksioma, 251 byte