how can i find partitions of given list?

Question

how can i find all partitions of list of integers? mostly i need algorithm that uses recursion as i'm gonna implement it in SML. i need just algorithm, i will do coding part by myself. by mistake i wrote code for finding subsets and i don't have too much time left for this

SML is kinda similar pascal so you get hang of format i'm gonna write in factorial for example is like this fun fuc x = if x<0 then 0 else if x=1 then 1 else x*(fac x-1)

thanks in advance

score 1 · Answer 1 · answered Dec 12 '12 at 23:40

1

The partition problem is a known NP-Hard problem (So there is no known polynomial solution for it), that can be solved using exhaustive search that is nicely written with recursion.

Pseudo code (tried to do it ML-like pseudo code, hope it helps and clear):

partition([],A,B): #base clause
   if (sum(A) == sum(B)):
        print (A,B) # this is a partition
partition(list, A,B):
   e <- head(list)
   partition(tail(list),e :: A,B)
   partition(tail(list),A, e :: B)

(if I remember correctly e :: A is adding an element to the beginning of A in ML, feel free to correct it if I remembered wrong)

answered Dec 12 '12 at 23:40

amit

175,853
27
231
333

sorry but i can't understand your code, only half of it. if you write in words how to it it will be better. e :: A is adding if A is list, and it goes like this e::[A] where e is element and A is list of elements. there is no print in ML as well. please comment every line, it will make things much easier for me. thanks in advance this example how it should work partition [1,2,3]; val it = [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]] – unknown Dec 12 '12 at 23:48
I dont think '@unknown is asking for a partition problem that you mentioned :) there is no constraint of equal summation to this problem – amas Dec 12 '12 at 23:51
i wrote code for finding all subsets if it will help in anything – unknown Dec 12 '12 at 23:55

score 1 · Answer 2 · edited May 23 '17 at 12:21

1

Check this out finding all the subsets. Basically in each permutation iteration you can get the other part of partition by subtracting the whole set from the union of the current subsets.

edited May 23 '17 at 12:21

Community

1
1

answered Dec 12 '12 at 23:55

amas

604
4
8

i already have code for finding subsets, okay i will try to do this way – unknown Dec 13 '12 at 00:12

score 1 · Answer 3 · answered Dec 13 '12 at 19:14

If you have a k-partition of a set S {S₁,...,S_n}, say {P₁,...,P_k}, you can generate k k-partitions of S &Union; {S_n+1}:

{P₁,..., P_i-1, P_i &Union; {n+1}, P_i+1,... P_k} for i in {1...k}

plus the (k+1)-partition P &Union; {k+1}

Call these the partitions generated from P. It's easy to demonstrate that all of the sets of partitions generated from two different partitionts of {1,...,n} are disjoint, and that every partition of {1,...,n+1} is generated from some partition of {1,...,n}.

I think that's enough to make the recursive solution to the problem obvious.

For verification, the count of the number of partitions of {1,...,n} is the B(n) where B is the Bell number, (Sloane A000110)

Andreas Rossberg · Answer 4 · 2012-12-13T22:46:06.853

Judging from your reply to amit, you seem to be looking for:

fun partitions [] = []
  | partitions [x] = [[[x]]]
  | partitions (x::xs) =
    let
       val zsss = partitions xs
    in
       map (fn zss => [x]::zss) zsss @
       map (fn zs::zss => (x::zs)::zss) zsss
    end

Edit: Sorry, I misread your earlier example as partition [1,2,3] = [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[1],[2],[3]]], i.e., ordered partitions.

Here is a solution to your actual question (I think):

fun extensions x [] = []
  | extensions x (xs::xss) =
    ((x::xs)::xss) :: map (fn zss => xs::zss) (extensions x xss)

fun partitions [] = [[]]
  | partitions (x::xs) =
    List.concat (map (fn zss => ([x]::zss) :: extensions x zss) (partitions xs))

how can i find partitions of given list?

4 Answers4