Permutations

• Tweet
• 

        Generates all permutation of n. Uses the naive (stupid) "let's generate all imaginable possibilities and see which are permutations" algorithm.

Time: O(n!)

#include <stdio.h>

int next(int v[], int n) {
	int i = n - 1;
	v[i] = v[i] + 1;
	while ((i >= 0) && (v[i] > n)) {
		v[i] = 1;
		i--;
		if(i >= 0)
			v[i]++;
	}

	if (i < 0)
		return 0;
	return 1;
}

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

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

int is_perm(int v[], int n) {
	int i, j;

	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (v[i] == v[j])
				return 0;

	return 1;
}

int main(int argc, char *argv[]) {
	int v[128];
	int n = 6;
	int i;
	for(i = 0; i <= n; i++)
		v[i] = i + 1;

	while (next(v,n))
		if (is_perm(v,n))
			printv(v,n);

	return 0;
}

Tags:
• C
• example
• naive
• permutation
• stupid