Partitions of a list

Question

The answer to this question is much too long

Your challenge is to write a partitioning function in the smallest number of characters.

Input example

['a', 'b', 'c']

Output example

[(('a'),('b'),('c')),
 (('a', 'b'), ('c')),
 (('a', 'c'), ('b')),
 (('b', 'c'), ('a')),
 (('a', 'b', 'c'))]

The input can be a list/array/set/string etc. whatever is easiest for your function to process

You can also choose the output format to suit yourself as long as the structure is clear.

Your function should work for at least 6 items in the input

Answer 1

GolfScript (43 chars)

{[[]]:E\{:v;{:^E+1/{^1$-\[~[v]+]+}/}%}/}:P;

or

{[[]]:E\{:v;{:^E+1/{^1$-\{[v]+}%+}/}%}/}:P;

Same input format, output format, and function name as Howard's solution. There's no brute forcing: this takes the simple iterative approach of adding one element from the input list to the partition each time round the outer loop.

Answer 2

GolfScript, 51 characters

{[[]]\{[.;]`{1$[1$]+@@`1$`{[2$]-@@[+]+}++/}+%}/}:P;

The script defines a variable P which takes an array from top of the stack and pushes back a list of all partitions, e.g.

[1 2] P            # => [[[1] [2]] [[1 2]]]
["a" "b" "c"] P    # => [[["a"] ["b"] ["c"]] [["b"] ["a" "c"]] [["a"] ["b" "c"]] [["a" "b"] ["c"]] [["a" "b" "c"]]]

It does also work on larger lists:

6, P ,p            # prints 203, i.e. Bell number B6
8, P ,p            # 4140

You may perform own tests online.

Answer 3

J, 51 characters

([:<a:-.~])"1~.((>:@i.#:i.@!)#l)<@;/."1[l=:;:1!:1[1

Takes input from the keyboard, items separated by spaces:

   ([:<a:-.~])"1~.((>:@i.#:i.@!)#l)<@;/."1[l=:;:1!:1[1
a b c
+-----+------+------+------+-------+
|+---+|+--+-+|+--+-+|+-+--+|+-+-+-+|
||abc|||ab|c|||ac|b|||a|bc|||a|b|c||
|+---+|+--+-+|+--+-+|+-+--+|+-+-+-+|
+-----+------+------+------+-------+

Answer 4

Haskell, 90 87 71 66

Saved 5 bytes thanks to nimi.

x#[]=[[[x]]]
x#(y:s)=((x:y):s):map(y:)(x#s)
p=foldr((=<<).(#))[[]]

Example:

*Main> p "abc"
[["abc"],["bc","a"],["ac","b"],["c","ab"],["c","b","a"]]

Answer 5

Python 2, 131 bytes

def P(L):
 if len(L)<2:yield[L];return
 for p in P(L[1:]):
	for n,s in enumerate(p):yield p[:n]+[[L[0]]+s]+p[n+1:]
	yield[[L[0]]]+p

Try it online

Uses this algorithm.