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]

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

 

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

 

[spibou]

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]

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 = p + p[j];
p[j] = p - p[j];
p = p - p[j];

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

if (i != 0 && i != 1){ /*inserting a char at the begining*/
c = p;
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;
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);
}

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
$

lovecreatesbeauty

 

[Richard Heathfield]

lovecreatesbeauty said:

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!

cnt = pmtgen(a, "abc");

$ 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?

 

[Bill Pursell]

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!

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

What advantage does that have over:
tmp = p;
p = 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]

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!

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

What advantage does that have over:
tmp = p;
p = 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

 

[lovecreatesbeauty]

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.

lovecreatesbeauty

 

[Peter Nilsson]

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.lang.c/msg/98c0260bb56e83f2

 

[Dann Corbit]

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

A web search for "permuation algorithm" will turn up plenty of examples.
I get 12,900 hits with this:
http://www.google.com/search?hl=en&q="permutation+algorithm"

 

[CBFalconer]

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

If you diligently search the google archives you will find out how
I generated the following:

[1] c:\dnld\scratch>jumble abcde
string="abcde", max=120, len=5
abcde abced abdce abdec abecd abedc acbde acbed
acdbe acdeb acebd acedb adbce adbec adcbe adceb
adebc adecb aebcd aebdc aecbd aecdb aedbc aedcb
bacde baced badce badec baecd baedc bcade bcaed
bcdae bcdea bcead bceda bdace bdaec bdcae bdcea
bdeac bdeca beacd beadc becad becda bedac bedca
cabde cabed cadbe cadeb caebd caedb cbade cbaed
cbdae cbdea cbead cbeda cdabe cdaeb cdbae cdbea
cdeab cdeba ceabd ceadb cebad cebda cedab cedba
dabce dabec dacbe daceb daebc daecb dbace dbaec
dbcae dbcea dbeac dbeca dcabe dcaeb dcbae dcbea
dceab dceba deabc deacb debac debca decab decba
eabcd eabdc eacbd eacdb eadbc eadcb ebacd ebadc
ebcad ebcda ebdac ebdca ecabd ecadb ecbad ecbda
ecdab ecdba edabc edacb edbac edbca edcab edcba

[1] c:\dnld\scratch>jumble abcdd
string="abcdd", max=120, len=5
abcdd abdcd abddc acbdd acdbd acddb adbcd adbdc
adcbd adcdb addbc addcb bacdd badcd baddc bcadd
bcdad bcdda bdacd bdadc bdcad bdcda bddac bddca
cabdd cadbd caddb cbadd cbdad cbdda cdabd cdadb
cdbad cdbda cddab cddba dabcd dabdc dacbd dacdb
dadbc dadcb dbacd dbadc dbcad dbcda dbdac dbdca
dcabd dcadb dcbad dcbda dcdab dcdba ddabc ddacb
ddbac ddbca ddcab ddcba

Hint: both a c program and a script are involved.

 

[Richard Heathfield]

lovecreatesbeauty said:

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

I claim no credit for the following code, which I've adapted from "Programs
and Data Structures in C", 2nd edition, by Leendert Ammeraal. My
contribution was little more than to make it readable. ;-) (I am being
unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of
doing things.)


#include <stdio.h>
#include <string.h>

void Permute(char *Perm,
size_t n,
size_t unchanged)
{
size_t outer = 0;
size_t inner = 0;
int temp = 0;

if(unchanged < n)
{
for(outer = unchanged; outer < n; outer++)
{
temp = Perm[outer];
for(inner = outer; inner > unchanged; inner--)
{
Perm[inner] = Perm[inner - 1];
}
Perm[unchanged] = temp;
Permute(Perm,
n,
unchanged + 1);

for(inner = unchanged; inner < outer; inner++)
{
Perm[inner] = Perm[inner + 1];
}
Perm[outer] = temp;
}
}
else
{
printf("%s\n", Perm);
}
}

int main(int argc, char **argv)
{
char Input[256] = {0};
size_t len = 0;

if(argc > 1)
{
len = strlen(argv[1]);
if(len > sizeof Input - 1)
{
fprintf(stderr, "word too long for demo - truncating\n");
argv[1][sizeof Input - 1] = '\0';
}
strcpy(Input, argv[1]);
len = strlen(Input);
}
else
{
len = 3;
strcpy(Input, "ABC");
}

Permute(Input, len, 0);

return 0;
}

 

[lovecreatesbeauty]

If you diligently search the google archives you will find out how
I generated the following:

I searched for the mathematic concept e.g. formula (A(m,n) = n! / (n -
m)!) which I have leant in school. But now I feel it is some complex
for my poor brain. I think it's better for me not to just search for an
answer. It will not be a shame for me to work it out alone, right? The
following is the second version of my function, it's still not correct.
Perhaps I can make it correct at the third version.

#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, m;
int cnt = 0;
char c;

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

for (i = 0; i < len; ++i){
for (j = i + 1; j < len; ++j){
c = p;
p = p[j];
p[j] = c;
strcpy(*dest++, p);
cnt++;

for (k = 0; k < len; ++k){
for (m = k + 1; m < len; ++m){
if (k != i && m != j){
c = p[k];
p[k] = p[m];
p[m] = c;
strcpy(*dest++, p);
cnt++;
}
}
}
}
}

free(p);
return cnt;
}

#include <stdio.h>

#define ROW 120
#define COL 6
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, "abcd");
printf("%d permutations\n", cnt);
for (i = 0; i < ROW; i++){
printf("%s\t", a);
}

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

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

[1] c:\dnld\scratch>jumble abcdd
string="abcdd", max=120, len=5
abcdd abdcd abddc acbdd acdbd acddb adbcd adbdc
adcbd adcdb addbc addcb bacdd badcd baddc bcadd
bcdad bcdda bdacd bdadc bdcad bdcda bddac bddca
cabdd cadbd caddb cbadd cbdad cbdda cdabd cdadb
cdbad cdbda cddab cddba dabcd dabdc dacbd dacdb
dadbc dadcb dbacd dbadc dbcad dbcda dbdac dbdca
dcabd dcadb dcbad dcbda dcdab dcdba ddabc ddacb
ddbac ddbca ddcab ddcba

It's very good that it can handle two same characters in the string but
there will not be total 120 entries.

lovecreatesbeauty

 

[lovecreatesbeauty]

I claim no credit for the following code, which I've adapted from "Programs
and Data Structures in C", 2nd edition, by Leendert Ammeraal. My
contribution was little more than to make it readable. ;-) (I am being
unfair to Mr Ammeraal - it's a fine book. I just happen to prefer my way of
doing things.)

<snip>

That program fails at this situation which seems to be overcome by
CBFalconer's program in another post in this thread.

$ ./a.out ABCC
0: ABCC
1: ABCC
2: ACBC
3: ACCB
4: ACBC
5: ACCB
<snip>
17: CCBA
<snip>
23: CCBA
$

lovecreatesbeauty

 

[Richard Heathfield]

lovecreatesbeauty said:

<snip>

That program fails at this situation

(repeated letter issue)

Ah, I didn't realise you needed uniqueness. That isn't a problem I've faced,
but I would probably solve it either by pouring the combinations into a
binary search tree or by passing the output through sort | uniq, depending
on the situation.

 

[lovecreatesbeauty]

Ah, I didn't realise you needed uniqueness. That isn't a problem I've faced,
but I would probably solve it either by pouring the combinations into a
binary search tree or by passing the output through sort | uniq, depending
on the situation.

Yes, thank you. If possible, I would like to read your masterpiece
again and see how those magic are applied to the code.

Your Sincerely
lovecreatesbeauty

 

[Richard Heathfield]

lovecreatesbeauty said:

Yes, thank you. If possible, I would like to read your masterpiece
again and see how those magic are applied to the code.

Well, you'd either change printf("%s\n", Perm); to a call to a binary search
tree insertion routine, or you'd just let the program run like this:

../perm daddy | sort | uniq

The latter generates the following output:

adddy
addyd
adydd
ayddd
daddy
dadyd
daydd
ddady
ddayd
ddday
dddya
ddyad
ddyda
dyadd
dydad
dydda
yaddd
ydadd
yddad
yddda

 

[Keith Thompson]

Well, you'd either change printf("%s\n", Perm); to a call to a binary search
tree insertion routine, or you'd just let the program run like this:

./perm daddy | sort | uniq

<OT>
or ./perm daddy | sort -u
</OT>

 

[CBFalconer]

lovecreatesbeauty said:

(repeated letter issue)

Ah, I didn't realise you needed uniqueness. That isn't a problem
I've faced, but I would probably solve it either by pouring the
combinations into a binary search tree or by passing the output
through sort | uniq, depending on the situation.

That was the script component I mentioned in my post. The OP has
obviously not bothered to look up my posting of the code yet. The
script part was:

sort | uniq | pr -a -T --columns=8