Generate all "unique" subsets of a set (not a powerset)

Question

Let's say we have a Set S which contains a few subsets:

- [a,b,c]
- [a,b]
- [c]
- [d,e,f]
- [d,f]
- [e]

Let's also say that S contains six unique elements: a, b, c, d, e and f.

How can we find all possible subsets of S that contain each of the unique elements of S exactly once?

The result of the function/method should be something like that:

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

Is there any best practice or any standard way to achieve that?

I would be grateful for a Pseudo-code, Ruby or Erlang example.

Answer 1

It sounds like what you are looking for are the partitions of a set/array.

One way of doing this is recursively:

• a 1 element array [x] has exactly one partition
• if x is an array of the form x = [head] + tail, then the partitions of x are generated by taking each partition of tail and adding head to each possible. For example if we were generating the partitions of [3,2,1] then from the partition [[2,1]] of [2,1] we can either add 3 to to [2,1] or as a separate element, which gives us 2 partitions [[3,2,1] or [[2,1], [3]] of the 5 that [1,2,3] has

A ruby implementation looks a little like

def partitions(x)
  if x.length == 1
   [[x]]
  else
    head, tail = x[0], x[1, x.length-1]
    partitions(tail).inject([]) do |result, tail_partition|
      result + partitions_by_adding_element(tail_partition, head)
    end
  end
end

def partitions_by_adding_element(partition, element)
  (0..partition.length).collect do |index_to_add_at|
    new_partition = partition.dup
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element]
    new_partition
  end
end

Answer 2

Why not to use the greedy algorithm?

1) sort set S descending using the subsets length
2) let i := 0
3) add S[i] to solution
4) find S[j] where j > i such as it contains of elements which are not in current solution
5) if you can't find element described in 4 then
5.a) clear solution
5.b) increase i
5.c) if i > |S| then break, no solution found ;( 5.d) goto 3

EDIT
Hmm, read again your post and come to conclusion that you need a Best-First search. Your question is not actually a partition problem because what you need is also known as Change-making problem but in the latter situation the very first solution is taken as the best one - you actually want to find all solutions and that's the reason why you should you the best-first search strategy approach.