Generate all Sublist Partitions

Question

Given a non-empty list of integers, output every possible partitioning of the list where each partition is a non-empty sublist.

So for the list [1, 2, 3, 4] the result is:

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

The order of the lists in the output does not matter, so [[1, 2, 3, 4]] could be first, last, or wherever. The order of the elements must be preserved.

This is code-golf, so shortest answer wins.

---

Related: Partition a list!

Answer 1

Retina, 27 19 bytes

Byte count assumes ISO 8859-1 encoding.

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

Try it online!

Explanation

Of course this computes all partitions using string processing. The basic idea is that we can generate all partitions by deciding for each , individually whether or not we want to split the list there. This kind of stuff can be done in Retina by matching each , in turn and using a replacement which gives both possible outputs.

The input acts as the base case: the partition where all elements are still in a single list.

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

Now we repeatedly (+) match the first (1) comma (,), on each line (%) (treating that line as a separate string, which is relevant for $' and ``$1 ` in the substitution).

That comma gets replaced with:

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

Remember that everything in front of the match and after the match remains in the string anyway, so the full result is actually $`;$'¶$`];[$' which explains why we insert the suffix and prefix in that order.

This loop stops once all commas are gone.

;
,

Finally, replace the semicolons with commas again to match the input format.

Answer 2

Pure Bash, 28

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

Here, lists are colon-separated, and contained in square brackets. For example in the question, the input list would be 1:2:3:4 and the output is:

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

Try it online.

• ${1//:/REPLACEMENT} replaces the colons in $1 with {:,]:[\}
• This generates a brace expansion like [1{:,]:[}2{:,]:[}3{:,]:[}4]
• The eval (and careful \ escapes) causes the brace expansion to happen last and give the desired result.

---

If it is necessary to exactly match the given [[ , , ...]] format, then we can do this instead:

Pure Bash, 47

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

Try it online.

Answer 3

Pyth, 2 bytes

./

With input [1, 2, 3, 4] (for instance).

Explanation: ./ is the partition operator. It returns all divisions of the input list into disjoint sub-lists. The input is implicitly fed to the program.

Test it online!

Answer 4

05AB1E, 5 bytes

Œæʒ˜Q

Try it 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

Answer 5

Python 3, 82 72 66 bytes

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

Try it online!

-5 bytes thanks to @JonathanAllan

Answer 6

Haskell, 59 55 49 bytes

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

Try it online!

Recursive solution. Usage example: p [1,2,3] returns [[[1,2,3]],[[1,2],[3]],[[1],[2,3]],[[1],[2],[3]]].

-6 bytes thanks to xnor!

Answer 7

J, 42 bytes

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

Generates all sublist partitons by creating the keys for partition sublists of length 1 and iterating to the length of the input list. Each partition sublist is then formed by selecting from the keys.

For example, here is the process of creating the keys for a length 4 list.

Try it online!

Answer 8

Brachylog, 2 bytes

~c

Try it online!

Function submission that produces output via acting as a generator. (The TIO link contains extra code to make this into a full program, for testing purposes.)

Incidentally, although not technically a builtin, this is so commonly used in Brachylog that a) it probably deserves a single-byte representation, and b) the c builtin can take a parameter to make assertions about its input (whereas with most builtins, a parameter talks about how to produce the output).

Explanation

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

Answer 9

J, 26 24 bytes

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

Try it online!

Answer 10

Jelly, 2 bytes

ŒṖ

Try it online!

Answer 11

APL, 26 bytes

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

Explanation:

• X←⍴1↓⍵: X is the length of ⍵ (the input list) with its first element dropped
• ⍳2*X: the numbers [1..2^X]
• (X⍴2)⊤: base-2 representation of those numbers, with X positions (i.e. X itself will wrap around to 0).
• ↓⍉: rotate the matrix and split it along the lines (⊤ gives as a result a matrix with the numbers along the columns), giving an array of bit vectors
• 1,¨: prepend a 1 to each bit vector.
• ⊂∘⍵¨: for each bit vector, split ⍵ at each 1.

Answer 12

Haskell, 45 bytes

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

Try it online!

I found this solution a while back in thinking about a Haskell tip.

Answer 13

Python, 90 bytes

outgolfed by ovs (making something I thought I'd tried work :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

A recursive function which builds up the list of partitions from slices of the input with the tail reached when the slices are of length 1.

Try it online!

The exec saves 4 bytes over a while or 3 over a for loop (below) since it means only two \ns rather than two levels of indentation, allowing the whole function to be on one line (while the order of slicing does not matter).

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

Answer 14

Python 3, 67 bytes

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

Try it online!

Answer 15

Haskell, 59 bytes

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

Answer 16

Ruby, 62 57 bytes

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

Try it online!

How it works:

• The number of partitions is 2^(n-1): I iterate on binary numbers in that range, take the groups of zeros and ones and map them as subsets of the initial list.
• Instead of fiddling with the range, I make it double and discard duplicates at the end. Now I can also discard the first binary digit and make the chunk function shorter.

Answer 17

Curry (PAKCS), 32 bytes

f(a:b++c:d)=(a:b):f(c:d)
f a=[a]

Try it online!

Curry supports non-deterministic operations which can return different values for the same input. This is a non-deterministic function whose different return values are the all sublist partitions.

Answer 18

APL(Dyalog Unicode), 15 bytes ^SBCS

Extracted from this answer of mine. Assumes index origin 0.

{⊂∘⍵¨~,⍳1+×⍳≢⍵}

Try it on APLgolf!

Answer 19

Vyxal, 7 bytes

ÞSṗ'f⁰⁼

Try it Online!

well it has a 2-byte builtin øṖ but it doesn't return all of the partitions...

How?

ÞSṗ'f⁰⁼
ÞS      # Get all sublists of the (implicit) input
  ṗ     # Powerset
   '    # Filter for:
    f   #  Flatten
     ⁰⁼ #  Is it equal to the input? (non-vectorizing)

Answer 20

JavaScript (ES6), 87 bytes

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

Explanation: b is the list of previous sublists, c is the current sublist, (which starts off as the first element of the array, since that must be in the first sublist) while d is the list of all sublists. The rest of the array elements are then recursively processed. In each case there are two options: either the next element is appended to the current sublist, or the current sublist is completed and the next element starts a new sublist. The recursive results are then concatenated together. When the array is exhausted, the list of list of all sublists is the result.

Answer 21

APL(NARS) 38 char, 76 bytes

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

this use the Nars function 11 1‼k k but is very slow, unusable for arg array of 9 elements already...

  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
    

this below is the function that not use the built in:

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 

we se the type each result:

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

I don't know how it works, it is only heuristic try...

Possible I make some error; both the functions build the partitions of the list whatever input and not only 1 2 ... n.

Answer 22

Axiom, 251 bytes

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)

If someone find something better...ungof and test:

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

If this is too much space say that and I remove examples...