2

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).

Fabio
  • 2,105
  • 16
  • 26
  • Do you want to generate all subsets, or *simply* (not so simple) to count them? – Damien Dec 20 '20 at 10:32
  • I want to generate all subsets. – Fabio Dec 20 '20 at 10:58
  • This is essentially the same question as https://stackoverflow.com/questions/30893292/generate-all-partitions-of-a-set/30898130#30898130 (phrased as a bit vector instead of as a set, but the algorithms are the same). – rici Dec 20 '20 at 16:28
  • @rici, I do not quite understand the question you refer to. For example, it states that the intersection of 2 partitions is the empty set, and then, as an example, it uses {1,2,3} and {1,2}, which clearly do not have an empty intersection. However, I voted up your answer to that question, which resemble very closely the algorithm I came up with myself. – Fabio Dec 21 '20 at 10:29
  • @fabio: i think the examples in the question were hard to read because they were run together; I added some new lines which might help. While I was doing that, I noticed that I had left a link to a functioning solution in a comment; remarkably the link is still good five years later: https://ideone.com/6vaXaN – rici Dec 21 '20 at 20:03
  • @rici, the source code you posted is clear. Essentially that generate recursively all possible partitions. I think the algorithm I describe below is more efficient for this specific problem, as some of the partitions are invalid. When I encounter an invalid partition, I branch it away early, thus skipping generation of any derived partition, which would also be invalid. – Fabio Dec 22 '20 at 02:46

2 Answers2

0

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

Ehsan Gerayli
  • 495
  • 2
  • 9
  • Sorry, I don't understand. How do you insure that one element og group 1 is orthogonal with one element of group 2? – Damien Dec 20 '20 at 10:33
  • What about all elements of group one alone, for example? Also, I do not need to count, I need to obtain the actual sets. – Fabio Dec 20 '20 at 10:57
0

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.

Fabio
  • 2,105
  • 16
  • 26