448,709 Members | 1,603 Online Need help? Post your question and get tips & solutions from a community of 448,709 IT Pros & Developers. It's quick & easy.

# Permutation problem

 P: n/a Hello Everybody, Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Jan 27 '06 #1
6 Replies

 P: n/a Rajesh wrote: Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Show us what you've come up with so far. Jan 27 '06 #2

 P: n/a Rajesh wrote: Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Yes, I can. I assume you have given it a try already, so a good start would be for you to show us the code you have written so far. -- :wq ^X^Cy^K^X^C^C^C^C Jan 27 '06 #3

 P: n/a Rajesh wrote: Hello Everybody, Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Well, here's something to play with, and think about. However, I don't believe this is what you're asking for [an arbitrary value of n being required?], but it may give you some ideas? void perm(int n) { int i, k, j, d = 0; for(i = 1; i <= n; ++i) for(j = 1; j <= n; ++j) for(k = 1; k <= n; ++k) printf("%4d (%d, %d, %d)\n", ++d, i, j, k); } The code above will produce all the possible 'triples' of n, e.g., if n is 4, you'll still get 4! outputs, but they'll be of this form: 1 (1, 1, 1) 2 (1, 1, 2) 3 (1, 1, 3) 4 (1, 1, 4) 5 (1, 2, 1) 6 (1, 2, 2) 7 (1, 2, 3) ... ... 58 (4, 3, 2) 59 (4, 3, 3) 60 (4, 3, 4) 61 (4, 4, 1) 62 (4, 4, 2) 63 (4, 4, 3) 64 (4, 4, 4) However, I imagine you'd really like quads for n = 4 ... 1 (1, 1, 1, 1) 2 (1, 1, 1, 2) 3 (1, 1, 1, 3) 4 (1, 1, 1, 4) 5 (1, 1, 2, 1) 6 (1, 1, 2, 2) 7 (1, 1, 2, 3) 8 (1, 1, 2, 4) 61 (4, 4, 4, 1) 62 (4, 4, 4, 2) 63 (4, 4, 4, 3) 64 (4, 4, 4, 4) As I say, I imagine that your program *should* be able to work with arbitrary values of 'n' [within the limits of sizeof int etc], e.g., using a fixed number of nested loops like this is not possible - you'll have to perhaps think recursively about the problem in that case. -- ============== *Not a pedant* ============== Jan 27 '06 #4

 P: n/a pemo wrote: As I say, I imagine that your program *should* be able to work with arbitrary values of 'n' [within the limits of sizeof int etc] Given how fast factorial grows, it is not possible to handle cases where n is larger than 15... Jan 27 '06 #5

 P: n/a In article "pemo" writes: Rajesh wrote: Hello Everybody, Can anybody help me in writing a C program to generate and print all possible combinations of n numbers. For eg. for 3 numbers(1,2,3) there turn out 3! combinations. (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Well, here's something to play with, and think about. However, I don't believe this is what you're asking for [an arbitrary value of n being required?], but it may give you some ideas? Not really. To get all permutations sequentially you have to realise that the best way to notate a permutation is in mixed base. The last digit is in base n, the last but one in base n-1, etc. But here is something: #include int fac(int n) { if(n == 0) return 1; return n * fac(n - 1); } int perm[N], used[N]; int num_to_perm(int num) { int i, k, d; for(i = 0; i < N; i++) used[i] = 0; perm - 0; for(i = 1; i < N; i++) { k = num % (i + 1); num = num / (i + 1); perm[i] = k; } for(i = N - 1; i >= 0; i--) { d = perm[i]; k = 0; while(used[k] || d > 0) if(!used[k++]) d--; used[k] = 1; printf("%3d", k + 1); } printf("\n"); } int main(void) { int i, max; max = fac(N); for(i = 0; i < max; i++) num_to_perm(i); } Compile with -DN=n, where n is the number of elements in a permutation. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ Jan 28 '06 #6

 P: n/a Hello Rajesh, Here is something to play with: #include #define N 5 int main(char *argv[],int argc) { char list={'a','b','c','d','e'}; permute(list,0,N); return(0); } void permute(char list[],int k, int m) { int i; char temp; if(k==m) { /* PRINT A FROM k to m! */ for(i=0;i

### This discussion thread is closed

Replies have been disabled for this discussion. 