Code generates all the combinations of n elements choosing k elements.

See this for definition.

See this for explanation.

#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) && (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 < 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 < 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;
}

Generates all the permutations of {1, 2, ..., n}.

See this for further explanations.

#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) && (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 < (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 < 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;
}

This code generates all the subsets of {1, 2, ..., n} and prints them.

This also contains a very fast binary counter implementation.

See this for further explanations.

#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 < 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 < n) && mask[i]; ++i)
		mask[i] = 0;

	if (i < 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 < 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;
}

Selectv returns the position of the nth smallest number in the list.

Selectv modifies the list.

#include <stdio.h>

typedef struct {
	int len;
	int e[102];
} List;

void printv(char *msg, List l) {
	printf("%s", msg);
	int i;
	for (i = 0; i < l.len; ++i)
		printf("%d ", l.e[i]);
	printf("\n");
}

int pivot(List *l, int p, int r) {
	int x = l->e[r];
	int i = p - 1;
	int j = r + 1;
	
	while (1) {
		do {
			++i;
		} while (l->e[i] < x);
		do {
			--j;
		} while (l->e[j] > x);
	
		//printf("%d %d\n", i, j);
		
		if (i < j) {
			int aux = l->e[i];
			l->e[i] = l->e[j];
			l->e[j] = aux;
		} else
			return i - 1;
	}
}


int selectv(List *l, int nrp, int p, int r) {
	//printf("p, r: %d, %d\n", p, r);
	//printf("nrp: %d\n", nrp);
	//printv("l: ", *l);
	
	if (p == r)
		return l->e[p];
	
	if (p < r) {
		int q = pivot(l, p, r);
		
		//getchar();
		
		if (q - p + 1< nrp)
			return selectv(l, nrp - (q - p) - 1, q + 1, r);
		return selectv(l, nrp, p, q);
	}
	return -1;
}

int main(int argc, char *argv[]) {
	List l;
	l.len = 100;
	int i;
	for (i = 0; i < l.len; ++i)
		l.e[i] = l.len - i;
	
	int nth = 56;
	printf("%d: %d\n", nth, selectv(&l, nth, 0, l.len - 1));
	
	//printv("L: ", l);
	
	return 0;
}

Qucksort written in C. Uses the Hoare partition algorithm.

typedef struct {
	int len;
	int elem[50240];
} vector;

void printv(char *str, vector v) {
	printf("%s", str);
	int i = 0;
	for (; i < v.len; ++i)
		printf("%d ", v.elem[i]);
	printf("\n");
}

#define MAX(a, b) ((a > b) ? (a) : (b))
#define MIN(a, b) ((a < b) ? (a) : (b))

int partition(vector *v, int p, int r) {
	int x;
	if (p + 3 < r)
		x = MIN(v->elem[p], MAX(v->elem[p+1], v->elem[p+2]));
	else
		x = v->elem[p];
	
	int i = p - 1;
	int j = r + 1;
	while (1) {
		do {
			--j;
		} while (v->elem[j] > x);
		do {
			++i;
		} while (v->elem[i] < x);

		if (i < j) {
			int aux = v->elem[j];
			v->elem[j] = v->elem[i];
			v->elem[i] = aux;
		} else
			return j;			
	}
}

void quicksort_real(vector *v, int p, int r) {
	if (p < r) {
		int q = partition(v, p, r);
		quicksort_real(v, p, q);
		quicksort_real(v, q + 1, r);
	}
}

void quicksort(vector *v) {
	printf("Quicksort...\n");
	quicksort_real(v, 0, v->len - 1);
}

Implements the classic Merge-sort algorithm.

Time: theta(lg(n))
Space: theta(n)

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

void printv(char* in, int *v, int n) {
	printf("%s", in);
	int i = 0;
	for (; i < n; ++i)
		printf("%d ", v[i]);
	printf("\n");
}

void merge(int *v, int p, int q, int r) {
	int i = p;
	int j = q + 1;
	
	int *tmp = (int*)malloc((r - p + 1) * sizeof(int));
	int k = 0;
	
	while ((i <= q) && (j <= r)) {
		if (v[i] < v[j])
			tmp[k++] = v[i++];
		else
			tmp[k++] = v[j++];
	}
	
	while (i <= q)
		tmp[k++] = v[i++];
	
	while (j <= r)
		tmp[k++] = v[j++];
	
	memcpy(v + p, tmp, (r - p + 1) * sizeof(int));
	free(tmp);
}

void mergeS(int *v, int p, int r) {
	if (p < r) {
		int q = (p + r) / 2;
		mergeS(v, p, q);
		mergeS(v, q + 1, r);
		merge(v, p, q, r);
	}
}

int main(int argc, char *argv[]) {
	int n = 10;
	int v[] = {9, 8, 7, 6, 5, 5, 4, 3, 2, 1};
	
	printv("V: ", v, n);
	mergeS(v, 0, n - 1);
	printv("V: ", v, n);
	
	return 0;
}

Calculates the Greatest Common Denominator (GCD) of an array of ints using a Divide at Impera approach.

Time: O(lg(n))
Memory: O(n)

#include <stdio.h>

int gcd(int a, int b) {
	int r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int gcdv(int *v, int p, int r) {
	if (r == p + 1) {
		//printf("%d,%d: %d\n", p, r, gcd(v[p], v[r]));
		return gcd(v[p], v[r]);
	}
	
	if (r == p) {
		//printf("%d: %d\n", r, v[r]);
		return v[p];
	}
	
	int q = (p + r) / 2;
	//printf("%d,%d: %d\n", p, r, gcd(gcdv(v, p, q), gcdv(v, q + 1, r)));
	return gcd(gcdv(v, p, q), gcdv(v, q + 1, r));
}

int main(int argc, char *argv[]) {
	int v[] = {45, 60, 125, 345, 65, 9875, 4555};
	
	printf("GCD: %d\n", gcdv(v, 0, 6));
	
	return 0;
}

// by kyle 2007.8.24 using java

package com.chapter2;

public class MergeSortV2 {

	/**
	 * @param args
	 */
	static void Merge(int A[],int p, int q, int r)
	{
		int n1 = q-p+1;
		int n2 = r-q;
		int L[] = new int[n1+2];
		int R[] = new int[n2+2];
		for(int i = 1; i <= n1; i++)
		{
			L[i] = A[p+i-1];
		}
		for(int j = 1; j <= n2; j++)
		{
			R[j] = A[q+j];
		}
		L[n1+1] = Integer.MAX_VALUE;
		R[n2+1] = Integer.MAX_VALUE;
		int i = 1;
		int j = 1;
		for(int k = p; k <= r; k++)
		{
			if(L[i] < R[j])
			{
				A[k] = L[i];
				i++;
			}
			else
			{
				A[k] = R[j];
				j++;
			}
		}
	}
	static void MergeSort(int A[],int p, int r)
	{
		if(p<r)
		{
			int q = (p+r)/2;
			MergeSort(A, p, q);
			MergeSort(A, q+1, r);
			Merge(A, p, q, r);
			
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int arr[] = {6,23,33,1,5,77};
		MergeSort(arr,1,5);
		for(int i = 0; i < 6; i++)
		{
			System.out.println(arr[i]);
		}
	}

}

Pollard's rho heuristic is a method used to find a number's factors. This is faster than the classic brute-force, try every number until sqrt(n) method, but it's results are highly unpredictable.

This just prints the factors.

import sys
import random

def Euclid(a, b):
  while b != 0:
    r = a % b
    a = b
    b = r
  return a

def PollardRho(n):
  i = 1
  x = random.randint(0, n - 1)
  y = x
  k = 2
  tried = set()
  tried.add(x)
  while True:
    i = i + 1
    x = (x ** 2 - 1) % n
    if x in tried:
      return
    tried.add(x)
    d = Euclid(y - x, n)
    if d != 1 and d != n:
      print d # d is a factor. Print it.
    if i == k:
      y = x
      k = 2 * k

def main(argv):
  PollardRho(int(argv[0]))

if __name__ == "__main__":
    main(sys.argv[1:])

The Miller-Rabin primality test.

MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not. This is an extremley fast algorithm designed to test very large numbers.

s is the number of tests to perform. The chance that Rabin-Miller is mistaken about a number (i.e. thinks it's prime, but it's not) is 2^(-s). So, a value of 50 for s is more than enough for any imaginable goal (2^(-50) is 8.8817841970012523e-16).

import sys
import random

def toBinary(n):
  r = []
  while (n > 0):
    r.append(n % 2)
    n = n / 2
  return r

def test(a, n):
  """
  test(a, n) -> bool Tests whether n is complex.

  Returns:
    - True, if n is complex.
    - False, if n is probably prime.
  """
  b = toBinary(n - 1)
  d = 1
  for i in xrange(len(b) - 1, -1, -1):
    x = d
    d = (d * d) % n
    if d == 1 and x != 1 and x != n - 1:
      return True # Complex
    if b[i] == 1:
      d = (d * a) % n
  if d != 1:
    return True # Complex
  return False # Prime

def MillerRabin(n, s = 50):
  """
    MillerRabin(n, s = 1000) -> bool Checks whether n is prime or not

    Returns:
      - True, if n is probably prime.
      - False, if n is complex.
  """
  for j in xrange(1, s + 1):
    a = random.randint(1, n - 1)
    if (test(a, n)):
      return False # n is complex
  return True # n is prime

def main(argv):
  print MillerRabin(int(argv[0]), int(argv[1]))

if __name__ == "__main__":
  main(sys.argv[1:])