permutation generation

[onkar]

How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
.....
...

..

[pemo]

onkar wrote:

How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
....
..

.

Go see Google Groups - search comp.lang.c for 'permutations' - finds 250+
results

--
==============
Not a pedant
==============

[Richard Heathfield]

onkar said:

How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab

Think of your array as being in two parts - the left part and the right
part. Initially, the left part is empty. (To keep track, just store the
number of elements in the left part.)

IF n - left > 0
take the right part, and rotate it one place.
Now recurse, for example Permute(s, n, left + 1).
Now rotate it back again.
ELSE
You have a permutation.
END IF

Have a go at it; if you get stuck, show us your best attempt and we'll do
what we can to help you fix it up.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[spibou]

onkar wrote:

How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
....
..

.

Is the array allowed to contain the same character more than once ?
If yes do you want all printed permutations to look different from
each other or are repeats ok ?

[lovecreatesbeauty]

Richard Heathfield wrote:

Think of your array as being in two parts - the left part and the right
part. Initially, the left part is empty. (To keep track, just store the
number of elements in the left part.)

IF n - left > 0
take the right part, and rotate it one place.
Now recurse, for example Permute(s, n, left + 1).
Now rotate it back again.
ELSE
You have a permutation.
END IF

Have a go at it; if you get stuck, show us your best attempt and we'll do
what we can to help you fix it up.

I write a function to populate the permutations based on an original
string. But it seems that I don't make the logic correct, the function
can not get all the permutations. It can only get a part of them,
others are missed. Comments are welcome, thanks in advance!

#include <string.h>
#include <stdlib.h>

int pmtgen(char *dest[], const char *src)
{
const int len = strlen(src);
char *p = malloc(len + 1);
int i, j, k;
int cnt = 0;
char c;

strcpy(p, src);
strcpy(*dest++, p);
cnt++; /*the original string*/

for (i = 0; i < len; ++i){
for (j = i + 1; j < len; ++j){ /*exchanging*/
p[i] = p[i] + p[j];
p[j] = p[i] - p[j];
p[i] = p[i] - p[j];

strcpy(*dest++, p);
cnt++;
strcpy(p, src);
}

if (i != 0 && i != 1){ /*inserting a char at the begining*/
c = p[i];
for (k = i; k > 0; --k){
p[k] = p[k - 1];
}
p[0] = c;

strcpy(*dest++, p);
cnt++;
strcpy(p, src);
}

if (i != len - 1 && i != len - 1 - 1){ /*appending a char at
the end*/
c = p[i];
for (k = i; k < len - 1; ++k){
p[k] = p[k + 1];
}
p[len - 1] = c;

strcpy(*dest++, p);
cnt++;
strcpy(p, src);
}
}
free(p);
return cnt;
}

#include <stdio.h>

#define ROW 12
#define COL 5
int main(void)
{
char *a[ROW];
int cnt;
int i, j;

for (j = 0; j < ROW; j++){
a[j] = malloc(COL);
if (!a[j]){
return 0;
}
}

cnt = pmtgen(a, "abc");

printf("%d permutations: ", cnt);
for (i = 0; i < ROW; i++){
printf("%s\t", a[i]);
}

for (j = 0; j < ROW; j++){
free(a[j]);
}

printf("\n");
return 0;
}

$ gcc -g -W -Wall -pedantic -ansi test.c
$ ./a.out
6 permutations: abc bac cba bca acb cab
$

lovecreatesbeau ty

[Richard Heathfield]

lovecreatesbeau ty said:

<snip>

I write a function to populate the permutations based on an original
string. But it seems that I don't make the logic correct, the function
can not get all the permutations. It can only get a part of them,
others are missed. Comments are welcome, thanks in advance!
<snip>
cnt = pmtgen(a, "abc");
<snip>
$ gcc -g -W -Wall -pedantic -ansi test.c
$ ./a.out
6 permutations: abc bac cba bca acb cab

You appear to have found six permutations of the three characters. Which
permutations do you think you missed?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Bill Pursell]

lovecreatesbeau ty wrote:

I write a function to populate the permutations based on an original
string. But it seems that I don't make the logic correct, the function
can not get all the permutations. It can only get a part of them,
others are missed. Comments are welcome, thanks in advance!
<snip>
for (i = 0; i < len; ++i){
for (j = i + 1; j < len; ++j){ /*exchanging*/
p[i] = p[i] + p[j];
p[j] = p[i] - p[j];
p[i] = p[i] - p[j];

What advantage does that have over:
tmp = p[i];
p[i] = p[j];
p[j] = tmp; ?

You save one declaration, but you add 3 arithmetic
operations, 4 array dereferences, and you make the
code less clear.

[Michael Mair]

Bill Pursell schrieb:

lovecreatesbeau ty wrote:

I write a function to populate the permutations based on an original
string. But it seems that I don't make the logic correct, the function
can not get all the permutations. It can only get a part of them,
others are missed. Comments are welcome, thanks in advance!

<snip>

for (i = 0; i < len; ++i){
for (j = i + 1; j < len; ++j){ /*exchanging*/
p[i] = p[i] + p[j];
p[j] = p[i] - p[j];
p[i] = p[i] - p[j];

What advantage does that have over:
tmp = p[i];
p[i] = p[j];
p[j] = tmp; ?

You save one declaration, but you add 3 arithmetic
operations, 4 array dereferences, and you make the
code less clear.

In addition, you risk signed overflow -- p is a char * and
char could be effectively signed char.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[lovecreatesbeauty]

Richard Heathfield wrote:

$ gcc -g -W -Wall -pedantic -ansi test.c
$ ./a.out
6 permutations: abc bac cba bca acb cab

You appear to have found six permutations of the three characters. Which
permutations do you think you missed?

$ gcc test.c
$ ./a.out
11 permutations: abcd bacd cbad dbca bcda acbd adcb
acdb abdc cabd dabc
$ gcc test.c
$ ./a.out
17 permutations: abcde bacde cbade dbcae ebcda bcdea acbde
adcbe aecdb acdeb abdce abedc cabde abdec abced dabce
eabcd
$

When the length of the base string is 4 or 5 (or more than 3, I guess),
e.g. "abcd" or "abcde", the result is not correct. For
"abcd", there should be total 24 permutations, for "abcde" 120
permutations (A(m,n) = n! / (n - m)!). I will continue to improve it.
Thanks.

lovecreatesbeau ty

[Peter Nilsson]

pemo wrote:

onkar wrote:

How to generate different permutations of n char array?
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
....
..

.

Go see Google Groups - search comp.lang.c for 'permutations' - finds 250+
results

Just give them the code already...

http://groups.google.com/group/comp....c0260bb56e83f2

--
Peter