Permutations: Difference between revisions

Content added Content deleted

Inline

@@ Line 272: / Line 272: @@
 =={{header|C}}==
+See [[wp:Permutation#Systematic_generation_of_all_permutations|lexicographic generation]] of permutations.
-Iterative method. Given a permutation, find the next in lexicographic order. Iterate until the last one.
-Here the main program shows letters and is thus limited to permutations of 26 objects. The function computing
-next permutation is not limited.
 <lang c>#include <stdio.h>
 #include <stdlib.h>
+int next_perm(int n, char *a) {
-/* Find next permutation in lexicographic order.
+#	define swap(i, j) {t = a[i]; a[i] = a[j]; a[j] = t;}
-Return -1 if already the last, otherwise 0.
+	int k, l, t;
-A permutation is an array[n] of value between 0 and n-1. */
-int nextperm(int n, int *perm) {
+	/* 1. Find the largest index k such that a[k] < a[k + 1]. If no such
-	int i,j,k,t;
+	      index exists, the permutation is the last permutation. */
+	for (k = n - 1; k && a[k - 1] >= a[k]; k--);
-	t = 0;
+	if (!k--) return 0;
-	for(i=n-2; i>=0; i--) {
-		if(perm[i] < perm[i+1]) {
-			t = 1;
-			break;
-		}
-	}
-	/* last permutation if decreasing sequence */
-	if(!t) {
-		return -1;
-	}
-	/* swap tail decreasing to get a tail increasing */
-	for(j=i+1; j<n+i-j; j++) {
-		t = perm[j];
-		perm[j] = perm[n+i-j];
-		perm[n+i-j] = t;
-	}
-	/* find min acceptable value in tail */
-	k = n-1;
-	for(j=n-2; j>i; j--) {
-		if((perm[j] < perm[k]) && (perm[j] > perm[i])) {
-			k = j;
-		}
-	}
-	/* swap with ith element (head) */
-	t = perm[i];
-	perm[i] = perm[k];
-	perm[k] = t;
+	/* 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is
-	return 0;
+	   such an index, l is well defined */
+	for (l = n - 1; a[l] <= a[k]; l--);
+	/* 3. Swap a[k] with a[l] */
+	swap(k, l);
+	/* 4. Reverse the sequence from a[k + 1] to the end */
+	for (k++, l = n - 1; l > k; l--, k++)
+		swap(k, l);
+	return 1;
 }
+int main(int argc, char **argv) {
+	char a[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
-int main(int argc, char **argv) {
+	if (argc < 2) {
+		printf("usage: %s n (1 <= n <= 26)\n", argv[0]);
-	int i, n, *perm;
+		return 0;
-	if(argc != 2) {
-		printf("perm n (1 <= n <= 26\n");
-		return 1;
 	}
-	n = strtol(argv[1], NULL, 0);
-	perm = (int *)calloc(n, sizeof(int));
-	for(i=0; i<n; i++) {
-		perm[i] = i;
-	}
-	do {
-		for(i=0; i<n; i++) {
-			printf("%c", perm[i] + 'A');
-		}
-		printf("\n");
-	} while(!nextperm(n, perm));
-	free(perm);
-	return 0;
-}</lang>
+	int n = atoi(argv[1]);
-Sample result :
+	if (n <= 0) n = 4;
+	if (n > 26) n = 26;
+	do { printf("%.*s\n", n, a); } while(next_perm(n, a));
-perm 3
+	return 0;
+}</lang>output<lang>% ./a.out 3
 ABC
 ACB
@@ Line 352: / Line 319: @@
 BCA
 CAB
-CBA
+CBA</lang>
 =={{header|C++}}==