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.

Thinskinned

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

Trothplight

Works great! But I found it hangs for anything equal or above 10 items. Any idea why? running partitions([1,2,3,4,5,6,7,8,9,10]) hangs ruby – Lixivium

The collections involved get big quite quickly - there are 115975 partitions of a 10 item array, still it only took a few seconds on my machine. If you are running this in irb, then it will try and display the result - not a good idea! – Trothplight

it actually hangs in rails s and while running under rspec from RubyMine. I am on Mac running Lion. My problem is actually more specialized than this, so I posted it here: #9733444 – Lixivium

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.

Humus

Answer 3

It seems like a classic "backtrack" excercise.

• #1: Order your sets amongst eacother, so the backtrack will not give solutions twice.
• #2: current_set = [], set_list=[]
• #3: Loop Run through all the set that have lower order mark than the last in the set_list, (or all if the set_list is empty). Let call it set_at_hand
• #4: If set_at_hand has no intersection with current_set
• #4/true/1: Union it to current_set, also add to set_list.
• #4/true/2: current_set complete? true: add set_list to the list of correct solutions. false: recurse to #3
• #4/true/3: remove set_at_hand from current_set and set_list
• #5: End of loop
• #6: return

Sporophore

Answer 4

generate all subsets

def allSubsets set
    combs=2**set.length
    subsets=[]
    for i in (0..combs) do
        subset=[]
        0.upto(set.length-1){|j| subset<<set[j] if i&(1<<j)!=0}
        subsets<<subset
    end
    subsets
end

Convene

Answer 5

take a look here: https://github.com/sagivo/algorithms/blob/master/powerset.rb
this is a simple algorithm i built to find a powerset of an array.

Lillielilliputian