Subset

Given a set S, what are their subset?, what are their k-subset?. I’ve compiled several Java methods which iterate over these subset. Due to its low efficiency, this technique only should be used in brute force algorithms.

Contents

Notation
All the subset
All the k-subset
Auxiliar methods
References

Notation

S is the set with elements {n1, n2, n3, ... nn}. The number of elements of S is |S|=n.

K is the subset of S {k1, k2, k3, ... kk}, where ki belongs to S and ki doesn’t represent the same element S that kj does, with 1<=i,j<=k. The number of elements of K is |K|=k and takes values from 0 to n.

The subset of S will be represented byt set of n elements of {0, 1}, where 1 means belonging and 0 means not belonging. The number of elements of the suset |K|=k is the number of 1's that it has.

(contents)

All the subset

All the subset of S have subset from 0 elements to n. There are 2ⁿ of subset.

All the subset.

|S|=3

K0={0,0,0}
K1={0,0,1}
K2={0,1,0}
K3={0,1,1}
K4={1,0,0}
K5={1,0,1}
K6={1,1,0}
K7={1,1,1}

allSubsetBit(int) (iterative)

/**
* Iterates over all the subset of a given set of n elements.
*
* The maximun number of elements of the given set is 63.
* Subset are represented at bit level, 1 means belonging,
* and 0 not belonging.
* @param n Number of elements of the set, 0<=n<=63. 
*/ 
public static void allSubsetBit(int n) {
  for (long i = 0, lim = 1L << n; i < lim; ++i) {
    printSubset(n, i);
  }
}

allSubsetArrayIterative(int) (iterative)

/**
* Iterates over all the subset of a given set of n elements.
*
* The size of the set doesn't have any restriction, but
* the memory heap size.
* The subset is represented by an array of booleans, where
* true means belonging, and false means not belonging.
* @param n Number of elements of the set, n<=0.
*/
public static void allSubsetArrayIterative(int n)  {

boolean[] subset = new boolean[n];

while (true) {

  printSubset(n, subset);

  // Add 1
  int i=0; 
  do {
    subset[i] = !subset[i]; 
    ++i;         
  } while (i<n && !subset[i-1]);

  if (i>=n && !subset[i-1]) break;   
}  
}

allSubsetArrayRecursive(int) (recursive)

/**
* Iterates over all the subset of a given set of n elements,
* recursive version.
*
* The size of the set doesn't have any restriction, but
* the memory heap size.
* The subset is represented by an array of booleans, where
* true means belonging, and false means not belonging.
* @param n Number of elements of the set, n<=0.
*/
public static void allSubsetArrayRecursive(int n) {
  boolean[] subset = new boolean[n];
  allSubsetArrayRecursion(n, subset, 0);
}

private static void allSubsetArrayRecursion(int n, boolean[] subset, int i) {

  if (i < n) {
    subset[i] = true;
    allSubsetArrayRecursion(n, subset, i + 1);
  
    subset[i] = false;
    allSubsetArrayRecursion(n, subset, i + 1);
  } else {
    printSubset(n, subset);
  }
}

(contents)

All the k-subset

All the subset of S with k elements. The number of k-subset is:

n! |k-subset|= (n-k)!·k!

All the k-subset.

|S|=5
k=3

K0={0,0,1,1,1}
K1={0,1,0,1,1}
K2={0,1,1,0,1}
K3={0,1,1,1,0}
K4={1,0,0,1,1}
K5={1,0,1,0,1}
K6={1,0,1,1,0}
K7={1,1,0,0,1}
K8={1,1,0,1,0}
K9={1,1,1,0,0}

The following code has been taken from the book Hacker's Delight by Henry S. Warren Jr. It is a bitwise trick for getting the next greater number than one given with the same number of 1’s in binary representation.

allSubsetKBit(int,int)

/**
* Iterates over all the subset of k elements in a set of n
* elements.
*
* The maximun number of elements of the given set is 63.
* k must be 0<k<=n.
* Subset are represented at bit level, 1 means belonging,
* and 0 not belonging.
* REF: Warren, Hackers Delight, p.14.
* @param n Number of elements of the set, 0<=n<=63.
* @param k Number of element of the subset, 0<k<=n.
*/
public static void allSubsetKBit(int n, int k) {

long subset = 0;
// Set 1 k first bits
for (int i=0; i<k; ++i) {
  subset |= 1<<i;
}

long limite = 1<<n;

long smallest, ripple, ones;
while (subset < limite) {
  printSubset(n, subset);
   
  // From Hacker's Delight
  // Next greater number with the same number of 1's.
  smallest = subset & -subset;
  ripple = subset + smallest;
  ones = subset ^ ripple;
  ones = (ones>>2)/smallest;
  subset = ripple | ones;
}
}

allSubsetKArrayIterative(int,int)

/**
* Iterates over all the subset of a given set of n elements,
* iterative version.
*
* The size of the set doesn't have any restriction, but
* the memory heap size.
* k must be 0<k<=n.
* The subset is represented by an array of booleans, where
* true means belonging, and false means not belonging.
* @param n Number of elements of the set. No restrictions.
* @param k Number of element of the subset, 0<=k<=n.
*/
public static void allSubsetKArrayIterative(int n, int k)  {
boolean[] subset = new boolean[n];

while (true) {

  int subsetCount = 0;
  for (int i=0; i<n; ++i) {
    if (subset[i]) {
      ++subsetCount;
    }
  }

  if (subsetCount==k) {
    printSubset(n, subset);
  }

  // Add 1
  int i=0; 
  do {
    subset[i] = !subset[i]; 
    ++i;         
  } while (i<n && !subset[i-1]);

  if (i>=n && !subset[i-1]) break;   
}  
}

allSubsetKArrayRecursive(int,int)

/**
* Iterates over all the subset of a given set of n elements,
* recursive version.
*
* The size of the set doesn't have any restriction, but
* the memory heap size.
* k must be 0<k<=n.
* The subset is represented by an array of booleans, where
* true means belonging, and false means not belonging.
* @param n Number of elements of the set. No restrictions.
* @param k Number of element of the subset, 0<k<=n.
*/
public static void allSubsetKArrayRecursive(int n, int k) {
boolean[] subset = new boolean[n];
allSubsetKArrayRecursion(n, k, subset, 0, 0);
}

private static void allSubsetKArrayRecursion(int n, int k, boolean[] subset, int subsetElements, int i) {

if (i < n) {
  subset[i] = true;
  allSubsetKArrayRecursion(n, k, subset, subsetElements+1, i+1);

  subset[i] = false;
  allSubsetKArrayRecursion(n, k, subset, subsetElements, i + 1);
} else {

  if (k==subsetElements) {
    printSubset(n, subset);
  }
}
}

(contents)

Auxiliar methods

These methods do a function with the subset given by the methods above. In this case, they print the subset. These are the methods that need to be changed for changing the behaviour.

printSubset(int,long)

/**
* Prints a subset represented with the bits of a long.
*
* @param n Maximum number of elements of the subset.
* @param subset Bit representation of the subset.
*/
private static void printSubset(int n, long subset) {
for (int j = n-1; j >= 0; --j) {
  System.out.printf("%d", ((subset & (1L << j)) != 0) ? 1 : 0);
}
System.out.printf("%n");
}

printSubset(int,boolean[])

/**
* Prints a subset represented by an array of booleans.
*
* @param n Maximum number of elementos of the subset.
* @param subset Subser represented by an array of booleans.
*/
private static void printSubset(int n, boolean[] subset) {
for (int j = n-1; j >= 0; --j) {
  System.out.printf("%d", (subset[j]) ? 1 : 0);
}
System.out.printf("%n");
}

(contents)

Referencess

"Hacker's Delight", by Henry S. Warren Jr.
"k-subconjuntos.".

(contents)