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.
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.
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.
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.
It sounds like what you are looking for are the partitions of a set/array.
One way of doing this is recursively:
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
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With