StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Kim, your problem description sounds very much like a (homework) attempt to describe the simplest solution for enumerating all k-combinations of a set of n elements - without giving the actual solution away too easily. Anyway, see below for my shot. I used Java but the important parts are not different from C.</p> <pre><code>public class Homework { /** * Prints all k-combinations of a set of n elements. Answer to this * question: http://stackoverflow.com/questions/2698551 */ public static void main(String[] args) { Combinations combinations = new Combinations(7, 3); System.out.printf( "Printing all %d %d-combinations of a set with %d elements:\n", combinations.size(), combinations.k, combinations.n); for (int[] c : combinations) System.out.println(Arrays.toString(c)); } /** * Provides an iterator for all k-combinations of a set of n elements. */ static class Combinations implements Iterable<int[]> { public final int n, k; public Combinations(int n, int k) { if (n < 1 || n < k) throw new IllegalArgumentException(); this.n = n; this.k = k; } @Override public Iterator<int[]> iterator() { return new Iterator<int[]>() { private int[] c; @Override public void remove() { throw new UnsupportedOperationException(); } @Override public int[] next() { if (c == null) { c = new int[k]; for (int i = 0; i < k; i++) c[i] = i; } else { int i = c.length - 1; while (i >= 0 && c[i] == n - k + i) i--; if (i < 0) throw new NoSuchElementException(); c[i]++; for (int j = i + 1; j < c.length; j++) c[j] = c[i] + j - i; } return c.clone(); // remove defensive copy if performance is more important } @Override public boolean hasNext() { return c == null || c[0] < n - k; } }; } /** * Returns number of combinations: n! / (k! * (n - k)!). */ public BigInteger size() { BigInteger s = BigInteger.valueOf(n); for (int i = n - 1; i > n - k; i--) s = s.multiply(BigInteger.valueOf(i)); for (int i = k; i > 1; i--) s = s.divide(BigInteger.valueOf(i)); return s; } } } </code></pre> <p>Here is the output for your example:</p> <pre><code>Printing all 35 3-combinations of a set with 7 elements: [0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 1, 6] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 2, 6] [0, 3, 4] [0, 3, 5] [0, 3, 6] [0, 4, 5] [0, 4, 6] [0, 5, 6] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 2, 6] [1, 3, 4] [1, 3, 5] [1, 3, 6] [1, 4, 5] [1, 4, 6] [1, 5, 6] [2, 3, 4] [2, 3, 5] [2, 3, 6] [2, 4, 5] [2, 4, 6] [2, 5, 6] [3, 4, 5] [3, 4, 6] [3, 5, 6] [4, 5, 6] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload