Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 639
skanatek Avatar asked Dec 27 '11 10:12

skanatek


People also ask

How do you generate all possible subsets of a set in C++?

Find all distinct subsets of a given set in C++ The set of all subsets is called power set. The power set has 2n elements. We will loop through 0 to 2n (excluding), in each iteration we will check whether the ith bit in the current counter is set, then print ith element.

How do I get all the subsets of a set in Python?

Python has itertools. combinations(iterable, n) which Return n length subsequences of elements from the input iterable. This can be used to Print all subsets of a given size of a set.

How do you print all the subsets of an array in Python?

Step 1: Run a loop till length+1 of the given list. Step 2: Run another loop from 0 to i. Step 3: Slice the subarray from j to i.


2 Answers

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
like image 65
Frederick Cheung Avatar answered Oct 02 '22 07:10

Frederick Cheung


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.

like image 36
SOReader Avatar answered Oct 02 '22 07:10

SOReader