Permutation problem

[Rajesh]

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).

[Nudge]

Re: Permutation problem

Rajesh wrote:[color=blue]
> 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).[/color]

Show us what you've come up with so far.

[Ico]

Re: Permutation problem

Rajesh <rajesh.nagpal@ gmail.com> wrote:[color=blue]
>
> 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).[/color]

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

[pemo]

Re: Permutation problem

Rajesh wrote:[color=blue]
> 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).[/color]

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*
==============

[Nudge]

Re: Permutation problem

pemo wrote:[color=blue]
> 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][/color]

Given how fast factorial grows, it is not possible to handle cases
where n is larger than 15...

[Dik T. Winter]

Re: Permutation problem

In article <drd6v4$m5j$1@n ews.ox.ac.uk> "pemo" <usenetmeister@ gmail.com> writes:[color=blue]
> Rajesh wrote:[color=green]
> > 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).[/color]
>
> 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?[/color]

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 <stdio.h>

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] - 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/

[Shastri]

Re: Permutation problem

Hello Rajesh,

Here is something to play with:

#include <stdio.h>
#define N 5


int main(char *argv[],int argc)
{
char list[5]={'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<N;i++ ){printf("%c",l ist[i]);}
printf("\n");
}
else
{
for(i=k;i<m;i++ )
{
/* swap(a[i],a[m-1]); */
temp=list[i];
list[i]=list[m-1];
list[m-1]=temp;

permute(list,k, m-1);

/* swap(a[m-1],a[i]); */

temp=list[m-1];
list[m-1]=list[i];
list[i]=temp;
}
}
}

Cheers
Shastri

Rajesh wrote:[color=blue]
> 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).[/color]