Rosetta Code

Permutations: Difference between revisions

Page Discussion

Permutations (view source)

Revision as of 02:09, 12 August 2011

346 bytes removed ,  12 years ago
→‎{{header|C}}: simplify
(→‎{{header|Erlang}}: Replace algorithm with more efficient one.)
(→‎{{header|C}}: simplify)
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 nextpermnext_perm(int n, intchar *perma) {▼
/* 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 ik,j,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 (il = n -2 1; i>a[l] <=0 a[k]; il--) {;
 
/* 3. Swap a[k] with a[l] */
swap(k, l);
 
/* 4. Reverse the sequence from a[k + 1] to the end */
▲ for (jk++, l = n -2 1; jl >i k; jl--), {k++)
swap(k, l);
return 01;▼
}
▲
int main(int argc, char **argv) {
char a[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 
int if main(int argc, char< **argv2) {
printf("permusage: %s n (1 <= n <= 26)\n", argv[0]);▼
int i, n, *perm;
▲ return -10;
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 = strtolatoi(argv[1], NULL, 0);
Sample result :
▲ if (argcn !<= 20) {n = 4;
if (n > 26) n = 26;
 
do { printf("%.*s\n", n, a); } while(next_perm(n, a));
perm 3
 
▲ return 10;
}</lang>output<lang>% ./a.out 3
ABC
ACB
Line 352 ⟶ 319:
BCA
CAB
CBA</lang>
 
=={{header|C++}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/158368"