Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Permutations

DZone's Guide to

Permutations

· ·
Free Resource
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 
  
   

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;
}

  
Topics:

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}