11
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ Can we omit the surrounding [...] in the output format? (As long as partitions are clearly separated, e.g. by linefeeds.) \$\endgroup\$ – Martin Ender May 18 '17 at 17:11
  • \$\begingroup\$ Input and output formats are flexible, but they should be the similar. So if the input list has its elements on one line, the output lists should, too. \$\endgroup\$ – mbomb007 May 18 '17 at 17:27
  • \$\begingroup\$ That's not what I mean. Have a look at the Bash answer. It uses : as the list separator but in the output, partitions themselves aren't wrapped in an additional pair of [...]. \$\endgroup\$ – Martin Ender May 18 '17 at 17:30
  • \$\begingroup\$ Or, asked differently: in your example format in the challenge, can I drop the first [ and last ] from each line? \$\endgroup\$ – Martin Ender May 18 '17 at 17:32
  • \$\begingroup\$ Is it okay, if my output lists are inside another list? like [[[1, 2]], [[1], [2]]...] \$\endgroup\$ – kalsowerus May 18 '17 at 17:36

19 Answers 19

2
\$\begingroup\$

Jelly, 2 bytes

ŒṖ

Try it online!

\$\endgroup\$
13
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, this is a very neat answer! \$\endgroup\$ – Adnan May 18 '17 at 18:43
  • 1
    \$\begingroup\$ @Adnan thanks, I'm also quite happy with it. Although it is everything but efficient :) \$\endgroup\$ – kalsowerus May 18 '17 at 20:39
  • \$\begingroup\$ Nice answer when there wasn't a builtin yet, +1 from me! Just leaving this for anyone else coming here in the future, but 05AB1E now has a 2-bytes builtin to get all partitions: : Try it online. \$\endgroup\$ – Kevin Cruijssen Oct 16 '18 at 8:08
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Oh my, I can't ^v again :( I actually tried something like this and it didn't work, I must've gone wrong somewhere. \$\endgroup\$ – Jonathan Allan May 18 '17 at 17:12
  • 1
    \$\begingroup\$ ...in which case lop off 5 more \$\endgroup\$ – Jonathan Allan May 18 '17 at 17:17
  • 1
    \$\begingroup\$ @JonathanAllan thanks a lot! I could save another byte by reusing the l in the end \$\endgroup\$ – ovs May 18 '17 at 17:22
  • \$\begingroup\$ This solution already exists here. I messaged @feersum in TNB after posting the question, so that he'd have a chance to post it. \$\endgroup\$ – mbomb007 May 18 '17 at 19:05
  • \$\begingroup\$ I didn't mean that you should undo it, I just meant that you beat him to it. It's your choice, of course. \$\endgroup\$ – mbomb007 May 18 '17 at 20:57
4
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ You can write the second line shorter with do notation: do a:b<-p r;[(x:a):b,[x]:a:b] (this changes the order of the lists). \$\endgroup\$ – xnor Oct 17 '18 at 2:35
  • 1
    \$\begingroup\$ Also, <*> does exactly what you want [\(a:b)->(x:a):b,([x]:)]<*>p r, though it's longer than do because the first lambda seems to need a pattern match. \$\endgroup\$ – xnor Oct 17 '18 at 2:45
3
\$\begingroup\$

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.

Example

Try it online!

\$\endgroup\$
3
\$\begingroup\$

J, 26 24 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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}
\$\endgroup\$
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 59 bytes

x#[]=[[[x]]]
x#(a:b)=[(x:a):b,[x]:a:b]
foldr((=<<).(#))[[]]
\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.