find all possible subsets satisfying a predicate

Question

I have a set S of N elements. Each element is represented by a string of bits of length L. For example, with L=5, S could be formed by { 01010, 01100, 10100, 00001 }

A pair of elements is compatible if they do not have any bit in common (i.e. if their bitwise AND is zero). For example:

01010 is not compatible with 01100, because 01010 & 01100 = 01000 (not zero)
01010 is compatible with 10100, because 01010 & 01010 = 00000 (zero)

A subset of S is compatible, if the pairwise bitwise AND of all its elements is zero. For example, the subset { 01010, 10100, 00001 } is compatible because all the below statements are true

 01010 & 10100 = 0
 01010 & 00001 = 0
 10100 & 00001 = 0

I want to find all possible compatible subsets of S. Given the example of S above, this would be:

{ 01010 }
{ 01100 }
{ 10100 }
{ 00001 }
{ 01010, 10100 }
{ 01010, 00001 }
{ 01100, 00001 }
{ 10100, 00001 }
{ 01010, 10100, 00001 }

What is the best algorithm to achieve that?

The problem could be restated in terms of a graph, where every element of S is a node and compatible elements are connected by edges. In this case the problem becomes that of finding all possible set of nodes fully connected (i.e. were a direct edge exist between each pair of nodes).

user_14679885 · Answer

You can use this approach

define L groups as following in group i put all the nodes which has bit 1 in it's i rank so the problem is selecting one or none from each group. obviously you can not take more than one element of each group *if some node has more than one bit 1 then it counts duplicated so we need to divide it's 1 count at the end

So the result count would be as following : (Count(L_1)+1) * (Count(L_2)+1) *... * (Count(L_L)+1) / (countOfOne(element1) * ...* countOfOne(elementN)) You should ignore all zero 00..00 elements in the division section

user_5800661 · Answer

I solved the problem and it might be useful to share the solution.

First I enumerate the elements in the set. For example:

S = { 0: 01010, 1: 01100, 2: 10100, 3: 00001 }

Now any subset can be defined by the set of indices in increasing order. For example

{ 01010, 00001 } -> {0, 3}

I define P as a pair of (indices, bitmask), where the bitmask is obtained via bitwise or of all elements in the subset. For example:

{ 01010, 00001 } -> ({0, 3}, 01011}

I describe the solutions G as a vector of P. I initialize this with all the subset containing only one element, which are certainly part of the solution.

G = [ {{0}, 01010}, {{1}, 01100}, {{2}, 10100}, {{3}, 00001} ]

Every compatible subset of n elements must be obtained from a compatible subset with n-1 elements adding a single element. That suggests the algorithm in pseudocode:

Let firstSol(n) be a function returning the index of the first solution of size n in G Let lastSol(n) be a function returning the index of the last solution of size n in G Let N be the size of S

int n = 1;
int s;
do
    s = nSolutions(G) 
    for (i = firstSol(n); i <= lastSol(n); ++i)
       {vec, mask} = G[n];
       for (j = vec[n-1] + 1; j < N; ++j)
          if (mask & S[j] == 0)
             append to G: {{vec, j}, mask | S[j}}
while (s < nSolutions(G))

The algorithm stops as soon as no new solution is found.

find all possible subsets satisfying a predicate

2 Answers