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:

[[a,b,c], [d,e,f]];
[[a,b,c], [d,f], [e]];
[[a,b], [c], [d,e,f]];
[[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.

Frederick Cheung · Accepted Answer · 2011-12-27T12:05:48.480

3

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

edited Dec 27 '11 at 12:05

answered Dec 27 '11 at 11:31

Frederick Cheung

83,189
8
152
174

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 – mbdev Mar 15 '12 at 21:39
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! – Frederick Cheung Mar 15 '12 at 22:02
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: http://stackoverflow.com/questions/9732944/get-all-possible-subsets-preserving-order – mbdev Mar 16 '12 at 06:34

SOReader · Answer 2 · 2011-12-27T12:09:38.630

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.

score 0 · Answer 3 · answered Apr 30 '15 at 19:16

0

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.

answered Apr 30 '15 at 19:16

Sagiv Ofek

25,190
8
60
55

score 0 · Answer 4 · answered Dec 27 '11 at 11:04

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

test30 · Answer 5 · 2012-03-08T19:56:27.993

0

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

edited Mar 08 '12 at 19:56

answered Mar 08 '12 at 17:07

test30

3,496
34
26

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

5 Answers5

Linked