Hi,
Could someone please point me to a parallel algorithm for generating all the subsets of a given set of integers in an array?
Regards
Isn’t that just ordinary binary counting? Each element of the set may be either included or excluded in the subset, so for a set of N elements you find 2[sup]N[/sup] different subsets?
Tera explained it well…
That basically can be summed up as (1+1)^N = NC0 + NC1 + NC2 + … NCN
NC0 - Stands for the number of ways of choosing 0 elements from a set of N elements = 1 = Empty Set
NC1 - Stands for the number of ways of choosing 1 element from a set of N elements = N Subsets containing 1 distinct element
…
…
Similarly,
NCK - Stands for number of ways of choosing K elements from a set of N elements…
…
…
…
Now arriving at each one of the term - NC0, NC1, NC2 … NCN is embarassingly parallel.
Thats the highest level of parallelism you can extract in this problem.
Note that it is NOT load balanced well. FYI.
For the next level of parallelism you need to look into each of the term to see what is parallel inside.
The ability to choose K elements from N elements is a recursive problem.
Let F(N,K) represent the number of ways K elements can be chosen from N elements.
F(N,K) = F(N,1)*F(N-1,K-1) / K!
i.e. First select 1 element and then select remaining K-1 elements from the rest.
The K! term avoids duplicates.
This gives us a clue on what algorithm we can follow.
Consider NC2 set. Let us arrange the elements in original Set as {S1, S2, S3 … , SN}
The subsets would be:
{S1,S2}, {S1, S3},…{S1,SN} = N-1 ways
{S2,S3}, {S2, S4},…{S2,SN} = N-2 ways
{S3,S4}, {S3, S5},…{S3,SN} = N-3 eays
.
.
.
{SN-1,SN} = 1 way
Total:
((N-1)*N)/2 ways
Now the formation of each of the subset can be assigned to a thread/group of threads.
Each thread can take advantage of the recurrence relation to build its power set.
They can work independently. Load sharing is a problem yet.