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 `{n`_{1}, n_{2}, n_{3}, ... n_{n}}

. The number of elements of `S`

is `|S|=n`

.

`K`

is the subset of `S`

`{k`_{1}, k_{2}, k_{3}, ... k_{k}}

, where `k`_{i}

belongs to `S`

and `k`_{i}

doesn’t represent the same element `S`

that `k`_{j}

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**^{n} of subset.

All the subset.

|S|=3

K_{0}={0,0,0}

K_{1}={0,0,1}

K_{2}={0,1,0}

K_{3}={0,1,1}

K_{4}={1,0,0}

K_{5}={1,0,1}

K_{6}={1,1,0}

K_{7}={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:

*All the k-subset.*

|S|=5

k=3

K_{0}={0,0,1,1,1}

K_{1}={0,1,0,1,1}

K_{2}={0,1,1,0,1}

K_{3}={0,1,1,1,0}

K_{4}={1,0,0,1,1}

K_{5}={1,0,1,0,1}

K_{6}={1,0,1,1,0}

K_{7}={1,1,0,0,1}

K_{8}={1,1,0,1,0}

K_{9}={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)