October 2007


Sudoku is that Japanese puzzle that requires you to fill in a grid of numbers. Here, I describe a general algorithm to solve these puzzles. Also provided is the source code in C++.

You can see a Sudoku board below. The goal is to fill in every empty cell with a number between 1 and 9 so that no number repeats itself on any line, column of zone (three-by-three marked square).

A sudoku board

If you’ve never solved a Sudoku before, now would be the time to do it. Wikipedia describes some useful strategies.

How do you approach a problem like this? The simplest way is from input to output. What’s your input? It’s a 9×9 matrix of numbers like this one:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

How do you store it in the programme? If you said as a matrix, you were close. A matrix is obvious, it’s easy to understand, but it’s a pain to code. Believe me when I say, it’s a lot easier to store it as an array of 9*9 elements. What else do you need? A variable to keep track of how many cells have been filled in (0 means empty board; 81 means full board). An array of bitsets to keep track of what digits can’t be used in each cell (I’ll explain a little later), and the setter and getter functions. As it happens, it’s also easier if you encapsulate it in a C++ class. Here’s the full code to the programme (sudoku.cpp). I’ll explain it all in a bit.

#include <iostream>
#include <fstream>

using namespace std;

class SudokuBoard;
void printB(SudokuBoard sb);

typedef unsigned int uint;

const uint MAXVAL = 9;
const uint L = 9;
const uint C = 9;
const uint S = L * C;
const uint ZONEL = 3;
const uint ZONEC = 3;
const uint ZONES = ZONEL * ZONEC;

const uint lineElements[L][C] = {
    { 0,  1,  2,  3,  4,  5,  6,  7,  8},
    { 9, 10, 11, 12, 13, 14, 15, 16, 17},
    {18, 19, 20, 21, 22, 23, 24, 25, 26},
    {27, 28, 29, 30, 31, 32, 33, 34, 35},
    {36, 37, 38, 39, 40, 41, 42, 43, 44},
    {45, 46, 47, 48, 49, 50, 51, 52, 53},
    {54, 55, 56, 57, 58, 59, 60, 61, 62},
    {63, 64, 65, 66, 67, 68, 68, 70, 71},
    {72, 73, 74, 75, 76, 77, 78, 79, 80}
};

const uint columnElements[C][L] = {
    { 0,  9, 18, 27, 36, 45, 54, 63, 72},
    { 1, 10, 19, 28, 37, 46, 55, 64, 73},
    { 2, 11, 20, 29, 38, 47, 56, 65, 74},
    { 3, 12, 21, 30, 39, 48, 57, 66, 75},
    { 4, 13, 22, 31, 40, 49, 58, 67, 76},
    { 5, 14, 23, 32, 41, 50, 59, 68, 77},
    { 6, 15, 24, 33, 42, 51, 60, 69, 78},
    { 7, 16, 25, 34, 43, 52, 61, 70, 79},
    { 8, 17, 26, 35, 44, 53, 62, 71, 80}
};

const uint zoneElements[S / ZONES][ZONES] = {
    { 0,  1,  2,  9, 10, 11, 18, 19, 20},
    { 3,  4,  5, 12, 13, 14, 21, 22, 23},
    { 6,  7,  8, 15, 16, 17, 24, 25, 26},
    {27, 28, 29, 36, 37, 38, 45, 46, 47},
    {30, 31, 32, 39, 40, 41, 48, 49, 50},
    {33, 34, 35, 42, 43, 44, 51, 52, 53},
    {54, 55, 56, 63, 64, 65, 72, 73, 74},
    {57, 58, 59, 66, 67, 68, 75, 76, 77},
    {60, 61, 62, 68, 70, 71, 78, 79, 80}
};

class SudokuBoard {
public:
    SudokuBoard() :
        filledIn(0)
    {
        for (uint i(0); i < S; ++i)
            table&#91;i&#93; = usedDigits&#91;i&#93; = 0;
    }

    virtual ~SudokuBoard() {
    }

    int const at(uint l, uint c) { // Returns the value at line l and row c
        if (isValidPos(l, c))
            return table&#91;l * L + c&#93;;
        else
            return -1;
    }

    void set(uint l, uint c, uint val) { // Sets the cell at line l and row c to hold the value val
        if (isValidPos(l, c) && ((0 < val) && (val <= MAXVAL))) {
            if (table&#91;l * C + c&#93; == 0)
                ++filledIn;
            table&#91;l * C + c&#93; = val;
            for (uint i = 0; i < C; ++i) // Update lines
                usedDigits&#91;lineElements&#91;l&#93;&#91;i&#93;&#93; |= 1<<val;
            for (uint i = 0; i < L; ++i) // Update columns
                usedDigits&#91;columnElements&#91;c&#93;&#91;i&#93;&#93; |= 1<<val;
            int z = findZone(l * C + c);
            for (uint i = 0; i < ZONES; ++i) // Update columns
                usedDigits&#91;zoneElements&#91;z&#93;&#91;i&#93;&#93; |= 1<<val;
        }
    }

    void solve() {
        try { // This is just a speed boost
            scanAndSet(); // Logic approach
            goBruteForce(); // Brute force approach
        } catch (int e) { // This is just a speed boost
        }
    }

    void scanAndSet() {
        int b;
        bool changed(true);
        while (changed) {
            changed = false;
            for (uint i(0); i < S; ++i)
                if (0 == table&#91;i&#93;) // Is there a digit already written?
                    if ((b = bitcount(usedDigits&#91;i&#93;)) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
                        int d(1); // Find the digit
                        while ((usedDigits&#91;i&#93; & 1<<d) > 0)
                            ++d;
                        set(i / C, i % C, d); // Fill it in
                        changed = true; // The board has been changed so this step must be rerun
                    } else if (bitcount(usedDigits[i]) == MAXVAL)
                        throw 666; // Speed boost
        }
    }

    void goBruteForce() {
        int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
        for (uint i(0); i < S; ++i)
            if (table&#91;i&#93; == 0) // Is there a digit already written?
                if ((max == -1) || (bitcount(usedDigits&#91;i&#93;) > bitcount(usedDigits[max])))
                    max = i;

        if (max != -1) {
            for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit
                if ((usedDigits&#91;max&#93; & 1<<i) == 0) { // If it can be placed in this cell, do
                    SudokuBoard temp(*this); // Create a new board
                    temp.set(max / C, max % C, i); // Complete the attempt
                    temp.solve(); // Solve it
                    if (temp.getFilledIn() == S) { // If the board was completely solved (i.e. the number of filled in cells is S)
                        for (uint j(0); j < S; ++j) // Copy the board into this one
                            set(j / C, j % C, temp.at(j / C, j % C));
                        return; // Break the recursive cascade
                    }
                }
        }
    }

    uint getFilledIn() {
        return filledIn;
    }

private:
    uint table&#91;S&#93;;
    uint usedDigits&#91;S&#93;;
    uint filledIn;

    bool const inline isValidPos(int l, int c) {
        return ((0 <= l) && (l < (int)L) && (0 <= c) && (c < (int)C));
    }

    uint const inline findZone(uint off) {
        return ((off / C / ZONEL) * (C / ZONEC) + (off % C / ZONEC));
    }

    uint const inline bitcount(uint x) {
        uint count(0);
        for (; x; ++count, x &= (x - 1));
        return count;
    }
};

void printB(SudokuBoard sb) {
    cout << "  |  -------------------------------  |" << endl;
    for (uint i(0); i < S; ++i) {
        if (i % 3 == 0)
            cout << "  |";
        cout << "  " << sb.at(i / L, i % L);
        if (i % C == C - 1) {
            if (i / C % 3 == 2)
                cout << "  |" << endl << "  |  -------------------------------";
            cout << "  |" << endl;
        }
    }
    cout << endl;
}

int main(int argc, char *argv&#91;&#93;) {
    SudokuBoard sb;

    ifstream fin("sudoku4.in");
    int aux;
    for (uint i(0); i < S; ++i) {
        fin >> aux;
        sb.set(i / L, i % L, aux);
    }
    fin.close();

    printB(sb);
    sb.solve();
    printB(sb);

    return 0;
}

Look at the main function. It first opens a file and then reads S ints from it. S is just the number of columns (C) multiplied by the number of lines (L). It reads the value into an auxiliary variable and then sets it in the SudokuBoard.

How does it set a cell? The relevant code is in set. The first line just checks if the parameters are valid (if the value’s not too large, if the specified cell does not exist, etc.). Then it checks if there’s a value already in the cell (there shouldn’t be). If not, it increments the number of filled-in cells.

Now things get intresting. If a certain cell contains the number n, it should be obvious that none of the cells on the same line, column or zone as the cell can contain n. Look at the board above: because there’s a 5 in cell 1,1, there can’t be any more fives in any of the cells on the first line, on the first column or in the upper-left zone. This is what the remainder of set does. It sets the nth bit in every bitset in whose corresponding cell the number n cannot appear.

Note: For a given cell, it’s trivial to find the line, column and zone in which it happens to be. What’s hard is to find the other cells in the same line, column or zone. To keep things simple, use three arrays of arrays that contain the number of the cells on a certain line, column or zone.

The next function of intrest is solve. If you’ll look at it, you’ll notice that it contains a tryexcept statement. As the comments clearly note, it’s just a speed boost. If you comment it out, the programme will still work (but in some cases a lot slower).

Solve calls two other functions: scanAndSet and goBruteForce. These are both algorithms to determine or guess what value should be placed in which cell.

scanAndSet
void scanAndSet() {
    int b;
    bool changed(true);
    while (changed) {
        changed = false;
        for (uint i(0); i < S; ++i)
            if (0 == table&#91;i&#93;) // Is there a digit already written?
                if ((b = bitcount(usedDigits&#91;i&#93;)) == MAXVAL - 1) { // If there's only one digit I can place in this cell, do
                    int d(1); // Find the digit
                    while ((usedDigits&#91;i&#93; & 1<<d) > 0)
                         ++d;
                    set(i / C, i % C, d); // Fill it in
                    changed = true; // The board has been changed so this step must be rerun
                } else if (bitcount(usedDigits[i]) == MAXVAL)
                    throw 666; // Speed boost
    }
}

The basic idea is this: we have a list of cells that need to be completed (those whose value is 0) and list of digits that cannot be placed in each cell. Go through the list of used digits, searching for a cell in which 8 digits cannot be placed (i.e. there’s only one digit that can be placed), and place it.

Now, every time you place a digit, you change the board a bit, restricting the digits that can be placed in other cells. So, you have to do the previous step until you don’t change anything any more.

There’s also a check in there if the number of used digits for any cell is 9 (i.e. no digit can be placed in the cell). If such a cell exists then the board is clearly wrong, so throw an exception (which is caught in the solve routine).

goBruteForce

void goBruteForce() {
int max(-1); // Find the cell with the _minimum_ number of posibilities (i.e. the one with the largest number of /used/ digits)
for (uint i(0); i < S; ++i) if (table[i] == 0) // Is there a digit already written? if ((max == -1) || (bitcount(usedDigits[i]) > bitcount(usedDigits[max])))
max = i;
if (max != -1) {
for (uint i(1); i <= MAXVAL; ++i) // Go through each possible digit if ((usedDigits[max] & 1<solve you’ll notice that there are some boards that are not completed by scanAndSet. Why? Because there are some boards that can’t be completed through logic alone (and ours isn’t particularly thorough either).

To get over this, you have to use a brute-force algorithm. The idea is simple enough: given the list of which digits cannot be placed in each cell, find the cell in which the minimum number of digits can be placed. For this cell, for every possible digit, write it down and try to solve the board.

This is where it becomes apparent why a C++ object-oriented approach is a smart move. Instead of writing the try in the current board and then having to keep track of what changes are made, simply clone the current board, fill in a cell and let it solve itself.

That’s it. You might want to try some of the other algorithms suggested on the Net. Good luck. Always open to comments.

In this article I’ll begin by defining binary numbers and describe the basic operations. Afterwords, I’ll show you several of the most common uses of binary numbers.

Humans work with digits in base 10, and we’re quite good at it. Computers, on the other hand, use base 2 and it shouldn’t come as a surprise that they’re extremely good at it. Today’s high level languages do a lot to hide this fact from us, but, still, a fairly good grasp of binary numbers is essential to working with computers, especially programming them.

Binary numbers

Mathworld defines binary as:

The base 2 method of counting in which only the digits 0 and 1 are used.

Basically, the binary representation of a number is the way of writing that number, uniquely, using only the digits 0 and 1. These are the binary representations of the first 16 natural numbers:
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

Given a number in base 10, how do you find the representation in base 2? You take the number and divide it repeatedly by 2 taking note of the remainder. After you’ve reached 0, write the remainders in reverse order. That’s the binary number! Here’s an example for 13:
Converting_13_to_binary

So,
13_in_binary

Now, how do you get a decimal form a binary? This is even easier. Take the number in binary form and start from the right side. Multiply the first digit (from the right side) with 20. Multiply the second digit with 21 and add it to the result from the first multiplication. Multiply the third digit with 22 and add it to what you have so far. … Do this for all the digits and you’ll get the decimal representation of the binary number.
13_binary_to_decimal

Logical operations

All of the following operations work in the same way. Take every bit form the first number and the corresponding bit from the second number (if it exists) and compute the resulting bit using the operation’s truth table.

NOT

NOT truth table

So, take each bit and reverse it.
0000 becomes 1111
0101 becomes 1010
1111 becomes 0000

It’s worthwhile to note that applying NOT twice, you get the original number unaltered.

AND

AND truth table

So, if both digits are 1 then the result is 1, otherwise it is 0.

OR

OR truth table

So, if either digit is 1, then the result is 1, otherwise it is 0.

XOR (eXclusive OR)

XOR truth table

So, if one of the digits it 1, but not both, then the result is 1, otherwise, the result is 0.

SHL (SHift Left) and SHR (SHift Right)

These aren’t like the other operations in that they don’t rely on truth tables. To apply them, simply drop the left-most (right-most) digit and add a 0 digit to the right (left).
After successive SHL operations,
0011 becomes 0110,
0110 becomes 1100,
1100 becomes 1000,
1000 becomes 0000

After successive SHR operations,
1100 becomes 0110,
0110 becomes 0011,
0011 becomes 0001,
0001 becomes 0000

Common use: Fast multiplication/division by 2

To quickly multiply an integer by 2, simply shift left the number.

To quickly divide an integer by 2, simply shift right the number.

In C, this would be:
a = a <> 1; /* Divide by 2 */
a = a >> 1; /* Multiply by 2*/

Setting/Checking a certain bit

To check whether the (n + 1)th bit is set (1) or not (0), use this:
a & 1<<n = 0 if the bit is NOT set
a & 1< 0 if the bit is set

To set the (n + 1)th bit, use this:
a = a | 1<<n;

What am I doing here? In both cases I first compute 1<<n. This is a binary number in which all digits are 0 but the nth digit is 1. Then, to check, I logically AND the two numbers. If the bit is set, then the result should be anything but 0. On the other hand, to set the bit, I logically OR the two numbers. If the bit was set, than this will have no effect. But if the bit was not set, it will be at the end.

Common use: bitsets

Chances are, at one time or another, you’ve had to use an array of boolean values. You’ve probably used something like this:
char foo[100];
foo[42] = 0; /* Equivalent of false */
foo[42] = 1; /* Equivalent of true*/

OR

bool bar[100];
bar[23] = false;
bar[23] = true;

This isn’t bad. Actually, in most cases it’s quite good. But if the number of elements is relatively small (less than 64), there’s a better way, that is using bitsets.

Instead of an array use an int, then use the methods described above to set and check the bits.
int a;
a = 0; /* The entire ``array" is set to false */
a |= 1<<3; /* The fourth bit is set */
if (a & 1<<3) /* Is the fourth bit set? */
a ^= 1<<3; /* If it is, flip it. */

Flipping bits

To flip a bit, XOR it by 1.
a ^= 1<<5; /* Flip the sixth bit */

Putting it all together: Printing a binary number

This small C programme prints out the binary representation of 0, 1, …, 16. (bit.c)

#include

/* Print n as a binary number */
void printbitssimple(int n) {
unsigned int i;
i = 1<<(sizeof(n) * 8 - 1); while (i > 0) {
if (n & i)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
}

/* Print n as a binary number */
void printbits(int n) {
unsigned int i, step;

if (0 == n) { /* For simplicity’s sake, I treat 0 as a special case*/
printf(“0000”);
return;
}

i = 1<<(sizeof(n) * 8 - 1); step = -1; /* Only print the relevant digits */ step >>= 4; /* In groups of 4 */
while (step >= n) {
i >>= 4;
step >>= 4;
}

/* At this point, i is the smallest power of two larger or equal to n */
while (i > 0) {
if (n & i)
printf(“1”);
else
printf(“0”);
i >>= 1;
}
}

int main(int argc, char *argv[]) {
int i;
for (i = 0; i < 16; ++i) { printf("%d = ", i); printbits(i); printf("\n"); } return 0; } [/sourcecode] Code should be fairly easy to understand. Good luck. Always open to comments. Update: The next article in this series is Counting Bits.

Checker Challenge is a very famous programming problem. It’s one of the first examples of backtracking anyone learns and variations of it frequently appare in contests.

In this article, I’ll present the classic algorithm for solving it and then a few optimisations to make it run less like a geriatric turtle.

First the problem:

Given a checker table of n lines and n columns, find all the ways of placing n checker pieces so that no two are on the same line, column or diagonal.

If n is greater or equal to 6 there is always at least one way to arrange the pieces. Usually there are a lot of ways (there are 73712 for n = 13).

For n = 6, this is one of the possible four arrangements:

| | O | | | | |
| | | | O | | |
| | | | | | O |
| O | | | | | |
| | | O | | | |
| | | | | O | |

First of all, you need a way to memorise the board. A matrix of n x n is the obvious solution, but it’s not really necessary. Notice that there can be at most one piece on any column, so it’s enough to use an array of n, each element containing the number of the row on which the corresponding element in the matrix is located. e.g. For the board above, the array would be {4, 1, 5, 2, 6, 3}.

Now, how do you approach such a problem? The simplest way (and, as it happens, the fastest) is to solve it recursively: first take the first column and attempt to place a piece on each of the n rows; for each of these, attempt to place a piece on each row of the second column; for every valid such arrangement, try to place a piece on each row of the third column; …; and so on until you place a piece on the nth column, at which point, you have a valid arrangement.

The key point in this algorithm is to know that when you’re working on the kth column, all the pieces on the first k – 1 columns form a valid arrangement.

As it happens, this is way to slow. For n = 10, I got tired of waiting and stopped the programme. If you do the math, you’ll see that for n, this algorithm does about nn recursive calls. This is bad, but if you write the checking routines inefficiently, you can easily make it slower by a factor of n.

There are three ways I know of to check if a position is valid (i.e. if a piece can be placed there). The first checks for validity after the piece has been placed, while the other two work by marking positions as invalid:

  1. The first is simple: let’s say you’ve reached column c and are wondering whether or not you can place a piece of row r. First take all the columns before c and check whether a piece is already on row r; afterwards, for every column c’ before c, and for every row r’ on that column check if abs(r – r’) = c – c’. If any of there conditions are true, than you can’t place a piece on row r.
  2. The second is just a way of trading memory for speed. Instead of doing as above, keep three vectors of boolean values (1 for the lines (usedRows) and 2 for the two types of diagonals (d1 and d2)), and for every piece you place on the board mark the corresponding elements in the three vectors as used. That is, mark rth element in rows, the n – c – 1 + r th element in d1 and the r + c th element in d2. If any of the corresponding elements for any position are marked, than that position is invalid.
  3. The third way is just combining the first two. For every row column c’ before c, supposing the piece is on row r’, mark the rows r’, r’ – (c – c’) and r’ + (c – c’) as invalid.

That’s it. For another speed boost, I use bitsets instead of vectors. Anyway, here’s the code in C (checker.c):

#include <stdio.h>
#include <string.h>

int q[14];

int sol[3][14];

int r = 0,
	d1 = 0,
	d2 = 0;

int solP = 0;

int n;

void gen_sol(int col) {
	if (col == n) {
		if (solP < 3)
			memcpy(sol&#91;solP&#93;, q, sizeof(int) * n);
		++solP;
		return;
	}

//NOTE Just calculating the non-admisible rows for this col every time is slightly faster than the "keep track of used rows and diagonals" solution
// 	int oc = 0;
// 	for (int i(0); i < col; ++i) {
// 		oc |= 1<<q&#91;i&#93;;
// 		oc |= 1<<(q&#91;i&#93; - (col - i));
// 		oc |= 1<<(q&#91;i&#93; + (col - i));
// 	}


	int i;
	for (i = 0; i < n; ++i) {
		if (!(r & 1<<i) && !(d1 & 1<<(n - col - 1 + i)) && !(d2 & 1<<(i + col))) {
			r |= 1<<i;
			d1 |= 1<<(n - col - 1 + i);
			d2 |= 1<<(i + col);
			
			q&#91;col&#93; = i;
			gen_sol(col + 1);

			r ^= 1<<i;
			d1 ^= 1<<(n - col - 1 + i);
			d2 ^= 1<<(i + col);
		}
	}
}

int main(int argc, char *argv&#91;&#93;) {
	n = 6;

	// Every solution's reflection is also a valid solution, so for the first
	// calculate only the first n/2 arrangements.
	int max = n;
	if (6 != n) {
		max = (n + 1) / 2;
	}
	
	// This complication appears because the odd values of n. Think about
	// it for a while and it will become obvious.
	int temp;
	int i;
	for (i = 0; i < max; ++i) {
		temp = solP;

		r |= 1<<i;
		d1 |= 1<<(n - 1 + i);
		d2 |= 1<<(i);

		q&#91;0&#93; = i;
		gen_sol(1);

		r ^= 1<<i;
		d1 ^= 1<<(n - 1 + i);
		d2 ^= 1<<(i);
	}

	int j;
	for (i = 0; i < 3; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", sol&#91;i&#93;&#91;j&#93; + 1);
		printf("\n");
	}

	if ((n % 2 == 0) && (6 < n))
		solP *= 2;
	else if ((n % 2 == 1) && (n > 6))
		solP += temp;
	printf("%d\n", solP);

	return 0;
}

There are a few other optimisations littered throughout the code, but they’re not hard to understand. Good luck. Always open to comments.

P.S. This also is also called “The Queens Problem” or the like.

Wikipedia defines combinations as:

In combinatorial mathematics, a combination is an un-ordered collection of unique elements. (An ordered collection is called a permutation.) Given S, the set of all possible unique elements, a combination is a subset of the elements of S. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears uniquely once); this is often referred to as “without replacement/repetition”. This is because combinations are defined by the elements contained in them, s the set {1, 1, 1} is the same as {1}. For example, from a 52-card deck any 5 cards can form a valid combination (a hand). The order of the cards doesn’t matter and there can be no repetition of cards.

Mathworld provides a more terse definition:

The number of ways of picking k unordered outcomes from n possibilities.

The combinations of n elements chosen as k is the number of unique ways of selecting k elements from a set of n.

From now on, by set of n I always mean one of the form {1, 2, 3, …, n}.

So, what are the ways of choosing 2 elements from a set of 4, {1, 2, 3, 4}?
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}

That’s 6 ways, but what is the general formula?
Formula for combinations of n chosen as k

This is easily proved: for a set of n, there are n ways of choosing the first element, n * (n – 1) ways of choosing the first two elements, …, n * (n – 1) * … * (n – k + 1) ways of choosing the first k elements. Unfortunately, this will generate duplicate subsets: for every subset of k elements, this will generate all the k! permutations of the subset. So, we have to divide the total number of subsets (n * (n – 1) * … * (n – k + 1)) by the number of repetitions (k!). This yields exactly the formula noted above.

Combinations are an astoundingly wide-spread concept, and are used in every branch of mathematics and especially in the analysis of algorithms. This said, there’s only one thing you really need to know: how to apply the formula.

Look at the formula above, notice that there are exactly k factors in the nominator and k factors in the denominator. So, to remember the formula and easily apply it:
P1. Draw the fraction line.
P2. Above the line, write k terms of the form: n, n - 1, n - 2, ...
P3. Below the line, write k terms of the form: 1, 2, 3, ...

Here are a few examples:
Combinations of 4 chosen as 1, 2, 3 and 4

And now for the fun part. How do you generate combinations? Look closely at the example above. First thing to note is that every combination is an array of k elements. Next, the first digit in every set is, basically, every digit between 1 and n. What about the other digits? They’re always between 1 and n and they’re always in ascending order. Now it should be obvious what the algorithm is:
P1. Start of with (1, 2, ..., k); this is the first combination.
P2. Print it.
P3. Given the combination (c0, c1, ..., cn), start from the back and for ci, if it is larger than n - k + 1 + i then increment it and go on to the next indice i. After this, if c0 > n - k, then this is not a valid combination so we stop. Otherwise give ci+1, ci+2, ... the values of ci + 1, ci+1 + 1, .... Jump to P2.

Here’s the sourcecode in C (comb1.c):
NOTE: Source is mangled by WordPress. Download the source file, or copy-paste it from here or remember to replace the amp-s with ampersands and the lt-s with “less then” signs.

#include <stdio.h>

/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
	printf("{");
	int i;
	for (i = 0; i < k; ++i)
		printf("%d, ", comb[i] + 1);
	printf("\\b\\b}\\n");
}

/*
	next_comb(int comb[], int k, int n)
		Generates the next combination of n elements as k after comb

	comb => the previous combination ( use (0, 1, 2, ..., k) for first)
	k => the size of the subsets to generate
	n => the size of the original set

	Returns: 1 if a valid combination was found
		0, otherwise
*/
int next_comb(int comb[], int k, int n) {
	int i = k - 1;
	++comb[i];
	while ((i >= 0) &amp;&amp; (comb[i] >= n - k + 1 + i)) {
		--i;
		++comb[i];
	}

	if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
		return 0; /* No more combinations can be generated */

	/* comb now looks like (..., x, n, n, n, ..., n).
	Turn it into (..., x, x + 1, x + 2, ...) */
	for (i = i + 1; i &lt; k; ++i)
		comb[i] = comb[i - 1] + 1;

	return 1;
}

int main(int argc, char *argv[]) {
	int n = 5; /* The size of the set; for {1, 2, 3, 4} it's 4 */
	int k = 3; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
	int comb[16]; /* comb[i] is the index of the i-th element in the
			combination */

	/* Setup comb for the initial combination */
	int i;
	for (i = 0; i &lt; k; ++i)
		comb[i] = i;

	/* Print the first combination */
	printc(comb, k);

	/* Generate and print all the other combinations */
	while (next_comb(comb, k, n))
		printc(comb, k);

	return 0;
}

Always open to comments. Have fun.

Wikipedia defines the partition of a set as:

In mathematics, a partition of a set X is a division of X into non-overlapping “parts” or “blocks” or “cells” that cover all of X. More formally, these “cells” are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.

A more succinct definition is given by Mathworld:

A set partition of a set S is a collection of disjoint subsets of S whose union is S.

Simply put, the partitions of a set S are all the ways in which you can choose disjoint, non-empty subsets of S that unioned result in S.

From now on, when I say a set of n elements, I mean {1, 2, …, n}. So, what are the subsets of {1, 2, 3}?
{1, 2, 3}
{2, 3} {1}
{1, 3} {2}
{3} {1, 2}
{3} {2} {1}

It’s obvious that these verify the definition: {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} and {1, 2, 3} are all subsets of {1, 2, 3}. They’re all non-empty and, in any partition, the same element never appears twice. Finally, in a partitioning, the union of the partitions is the original set.

In how many ways can you partition a set of n elements? There are many ways to calculate this, but as far as I can tell, the easiest is using Catalan numbers:
Formula for the nth Catalan Number

If you check the formula for 3 you’ll see that it does give the correct answer: 5.

A reader pointed out that what we may need here are not Catalan numbers, but Bell numbers. Wikipedia’s definition seems to agree with him.

Ok. We know what a partitioning is, we know how many there are, but how do you generate them? This is the first algorithm I could think of. It may not be clear from the explanation why it works but try it on a piece of paper for n=3 and it will become obvious. Here’s how I came up with it:

First of all, how do you represent a partitioning of a set of n elements? The straight-forward way would be using a vector of n integers, each integer representing the number of the subset in which the corresponding element is in. If the corresponding element of 3 is 2, that means that 3 is in the 2nd subset. So, given the set {1, 2, 3}:
Partitioning -> Encoding
{1, 2, 3} -> (1, 1, 1)
{1} {2, 3} -> (2, 1, 1)
{2} {1, 3} -> (1, 2, 1)
{1, 2} {3} -> (2, 2, 1)
{1} {2} {3} -> (3, 2, 1)

Notice that the encodings, written backwards are: 111, 112, 121, 122 and 123. From this you can guess how the generator works: more or less, generate all the numbers between 111 and 123 using only the digits 1, 2 and 3:

111
112
113
121
122
123

That’s almost right. The encodings (1, 1, 2) and (1, 1, 3) translate into the same partitioning: {1} {2, 3}. If you do the same thing for a larger n you’ll notice this happening again and again. Fortunately, there’s an easy solution: never use a digit that’s more than 1 larger than any other digit in the encoding. i.e. You can’t use (1, 1, 3) because 3 is larger by 2 than the other digits in the encoding (1 and 1).

To do this, I use another vector m with the following significance: m[i] is the largest of the first i elements in the encoding. This makes it very easy not to generate any duplicate partitionings.

Here’s the code in C (part.c):

#include <stdio.h>

/*
	printp
		- print out the partitioning scheme s of n elements 
		as: {1, 2, 4} {3}
*/
void printp(int *s, int n) {
	/* Get the total number of partitions. In the exemple above, 2.*/
	int part_num = 1;
	int i;
	for (i = 0; i < n; ++i)
		if (s&#91;i&#93; > part_num)
			part_num = s[i];

	/* Print the p partitions. */
	int p;
	for (p = part_num; p >= 1; --p) {
		printf("{");
		/* If s[i] == p, then i + 1 is part of the pth partition. */
		for (i = 0; i < n; ++i)
			if (s&#91;i&#93; == p)
				printf("%d, ", i + 1);
		printf("\\b\\b} ");
	}
	printf("\\n");
}

/*
	next
		- given the partitioning scheme represented by s and m, generate
		the next

	Returns: 1, if a valid partitioning was found
		0, otherwise
*/
int next(int *s, int *m, int n) {
	/* Update s: 1 1 1 1 -> 2 1 1 1 -> 1 2 1 1 -> 2 2 1 1 -> 3 2 1 1 ->
	1 1 2 1 ... */
	/*int j;
	printf(" -> (");
	for (j = 0; j &lt; n; ++j)
		printf("%d, ", s[j]);
	printf("\\b\\b)\\n");*/
	int i = 0;
	++s[i];
	while ((i < n - 1) &amp;&amp; (s&#91;i&#93; > m[i] + 1)) {
		s[i] = 1;
		++i;
		++s[i];
	}

	/* If i is has reached n-1 th element, then the last unique partitiong
	has been found*/
	if (i == n - 1)
		return 0;

	/* Because all the first i elements are now 1, s[i] (i + 1 th element)
	is the largest. So we update max by copying it to all the first i
	positions in m.*/
	int max = s[i];
	for (i = i - 1; i >= 0; --i)
		m[i] = max;

/*	for (i = 0; i &lt; n; ++i)
		printf("%d ", m[i]);
	getchar();*/
	return 1;
}

int main(int argc, char *argv[]) {
	int s[16]; /* s[i] is the number of the set in which the ith element
			should go */
	int m[16]; /* m[i] is the largest of the first i elements in s*/

	int n = 3;
	int i;
	/* The first way to partition a set is to put all the elements in the same
	   subset. */
	for (i = 0; i &lt; n; ++i) {
		s[i] = 1;
		m[i] = 1;
	}

	/* Print the first partitioning. */
	printp(s, n);

	/* Print the other partitioning schemes. */
	while (next(s, m, n))
		printp(s, n);

	return 0;
}

The code is heavily commented, but I’ll happily respond to any questions. This is also what I used to generate all the above listings. Try decommenting some of the code to see how the programme works. Good luck!

P.S. Every encoding after (3, 2, 1) yields a duplicate partitioning. For fun, try proving this mathematically.

There quite a few definitions of what a set is, but it all boils down to this:

A set defined as a collection of distinct elements, in which order is not important.

So {1, 2, 3}, {3, 4}, {} and {5, 99, -1} are all sets. Because the order of the elements is ignored, {1, 2, 3} and {3, 2, 1} is the same set. In case you’re wandering, there are exactly n! diffrent ways to write a set of n elements.

For the rest of the discussion, I’ll use sets of the form {1, 2, …, n}, so when I say a set of 3 elements, I mean {1, 2, 3}. Just remember that is not a property of sets. They can contain anything as elements, not necessarily consecutive numbers.

The set S1 is said to be the subset of the set S2, if all the elements of S1 also belong to S2.

Knowing this, it’s easy to figure out the subsets of {1, 2, 3}:
{ }
{ 1 }
{ 2 }
{ 1, 2 }
{ 3 }
{ 1, 3 }
{ 2, 3 }
{ 1, 2, 3 }

How many subsets are there? For a set of one element, there are 2 subsets: {} and {1}. For a set of 2 elements, there are 4 subsets: {}, {1}, {2}, {1, 2}. For a set of 3 elements, there are 8 subsets. Notice the pattern?
n = 1: 21
n = 2: 22
n = 3: 23

For a set of n there are 2n subsets. This is easily proved: Any subset of the set can either contain or not contain an element; so, for a subset, there are 2 states for the first element, 2 for the second element, …, 2 for the nth element; so, there are 2 states for the first element, 2 * 2 = 22 states for the first two, 2 * 2 * 2= 23 states for the first three, …, 2 * 2 * 2 * … * 2 = 2n states for all the n elements.

The problem here is how to generate all the subsets of a given set. There are a few algorithms for doing this, but in the end, only two are worth considering.

The first is this: given all the subsets of S and the element y, you can generate all the subsets of S U {y} by taking each subset of S, once adding to it y and once leaving it as it is. i.e. Knowing that {1, 3} is a subset of S, you obtain the following two subsets of S U {y}: {1, 3, y} and {1, 3}.

This does what it’s supposed to – it generates all the subsets of S, and it wastes no time. It can also be used as another way to prove that there are 2n subsets for any set of n elements. The only problem is that you need the subsets from the previous step to generate those of this step. This means that just before the end, you must have 2n – 1 subsets in memory. Considering how much memory computers have this days, it’s not particularly wasteful, but still, there’s a better way.

The better way involves using a mask. If you have the a set of n elements, a valid mask would be an array of n boolean (true/false; 1/0) elements. When you apply a mask to a set, you check each element (e) in the set and the corresponding one in the mask (m): if m is true(1), you add e to the result, otherwise, you ignore it. After applying the mask (0, 1, 0, 0, 1) to {1, 2, 3, 4, 5}, you get {2, 5}.

So, to generate all the subsets of a set of n elements, you first have to generate all the possible 2n masks of the set and then apply them.

Generating the masks is a simple problem. Basically, you just have to implement a binary counter, i.e. something that generates:
000
001
010
011
100
101
110
111

Here’s the code in C (sub.c):

#include <stdio.h>

/* Applies the mask to a set like {1, 2, ..., n} and prints it */
void printv(int mask[], int n) {
	int i;
	printf("{ ");
	for (i = 0; i &lt; n; ++i)
		if (mask[i])
			printf("%d ", i + 1); /*i+1 is part of the subset*/
	printf("\\b }\\n");
}

/* Generates the next mask*/
int next(int mask[], int n) {
	int i;
	for (i = 0; (i &lt; n) &amp;&amp; mask[i]; ++i)
		mask[i] = 0;

	if (i &lt; n) {
		mask[i] = 1;
		return 1;
	}
	return 0;
}

int main(int argc, char *argv[]) {
	int n = 3;

	int mask[16]; /* Guess what this is */
	int i;
	for (i = 0; i &lt; n; ++i)
		mask[i] = 0;

	/* Print the first set */
	printv(mask, n);

	/* Print all the others */
	while (next(mask, n))
		printv(mask, n);

	return 0;
}

Note: The next() function generates the bits in reverse order.

Always open to comments.

Last time, we defined what permutation is and gave a few basic properties.

In a few minutes we’ll see another algorithm for generating them, but first a little theory.

Lexicographical order is defined by Wikipedia as:

In mathematics, the lexicographic or lexicographical order, (also known as dictionary order, alphabetic order or lexicographic(al) product), is a natural order structure of the Cartesian product of two ordered sets.

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as
(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and b ≤ b′).

The result is a partial order. If A and B are totally ordered, then the result is a total order also.

More generally, one can define the lexicographic order on the Cartesian product of n ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

Mathworld adds the following regarding permutations and sets:

When applied to permutations, lexicographic order is increasing numerical order (or equivalently, alphabetic order for lists of symbols; Skiena 1990, p. 4). For example, the permutations of {1,2,3} in lexicographic order are 123, 132, 213, 231, 312, and 321.

When applied to subsets, two subsets are ordered by their smallest elements (Skiena 1990, p. 44). For example, the subsets of {1,2,3} in lexicographic order are {}, {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}.

An easy way to determine if a set is lexicographically after another is to interpret them as numbers in base n, where n is the largest element the set contains. So, (2, 1, 3) is after (1, 2, 3) because 213 < 123. Note: You may also choose n as any number greater than the largest element of the set. This is particularly convenient as most would rather use numbers in base 10 and not base 3.

Ok, but what does this have to do with permutations? Well, generating permutations in any order isn’t enough; you must generate them in lexicographic order.

Now, if you run last times’ algorithm, you find that, for n = 3, it prints:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Now, 123 < 132 < 213 < 231 < 312 < 321. So, the permutations are in lexicographic order!

The worst algorithm for any problem is usually called naive, but a more adequate adjective for the last algorithm would be retarded. It’s the slowest one I can think of, but it’s extraordinarily easy to explain.

This algorithm is slightly faster (about twice as fast) than the last one. It’s quite complex and harder to understand. It does the same thing as the last one, but where the naive algorithm just generated all possible sets, this one generates only valid permutations.

Here it is:

P1. Given n, we start with the first imaginable permutation p = (1, 2, ..., n) from the lexicographic point of view.

P2. Print the the permutation p or use it for something else.

P3. Let's say we have already build the permutation p = (p1, p2, ..., pn). In order to obtain the next permutation, we must first find the largest index i so that Pi<Pi + 1. Then, the element, Pi will be swapped with the smallest of the elements after Pi, but not larger than Pi. Finally, the last n - i elements will be reversed so that they appear in ascending order. Then, jump to P2.

That’s it for the algorithm, here’s the code in C (lexicoPerm.c):

#include <stdio.h>

void printv(int v[], int n) {
	int i;

	for (i = 0; i < n; i++)
		printf("%d ", v[i]);
	printf("\\n");
}

/*!
	This just swaps the values of a and b

	i.e if a = 1 and b = 2, after

		SWAP(a, b);

	a = 2 and b = 1
*/
#define SWAP(a, b) a = a + b - (b = a)

/*!
	Generates the next permutation of the vector v of length n.

	@return 1, if there are no more permutations to be generated

	@return 0, otherwise
*/
int next(int v[], int n) {
	/* P2 */
	/* Find the largest i */
	int i = n - 2;
	while ((i >= 0) &amp;&amp; (v[i] > v[i + 1]))
		--i;

	/* If i is smaller than 0, then there are no more permutations. */
	if (i < 0)
		return 1;

	/* Find the largest element after vi but not larger than vi */
	int k = n - 1;
	while (v[i] > v[k])
		--k;
	SWAP(v[i], v[k]);

	/* Swap the last n - i elements. */
	int j;
	k = 0;
	for (j = i + 1; j &lt; (n + i) / 2 + 1; ++j, ++k)
		SWAP(v[j], v[n - k - 1]);

	return 0;
}

int main(int argc, char *argv[]) {
	int v[128];
	int n = 3;

	/* The initial permutation is 1 2 3 ...*/
	/* P1 */
	int i;
	for (i = 0; i &lt; n; ++i)
		v[i] = i + 1;
	printv(v, n);

	int done = 1;
	do {
		if (!(done = next(v, n)))
			printv(v, n); /* P3 */
	} while (!done);

	return 0;
}



The code is commented and it does nothing but implement the algorithm. Have fun!

Next Page »