By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,897 Members | 1,955 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,897 IT Pros & Developers. It's quick & easy.

permutation generation

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

..

Jun 19 '06 #1
Share this Question
Share on Google+
27 Replies


P: n/a
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
==============
Jun 19 '06 #2

P: n/a
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)
Jun 19 '06 #3

P: n/a

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 ?

Jun 19 '06 #4

P: n/a
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
$

lovecreatesbeauty

Jun 19 '06 #5

P: n/a
lovecreatesbeauty 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)
Jun 19 '06 #6

P: n/a

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

Jun 19 '06 #7

P: n/a
Bill Pursell schrieb:
lovecreatesbeauty 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.
Jun 19 '06 #8

P: n/a
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.

lovecreatesbeauty

Jun 20 '06 #9

P: n/a
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

Jun 20 '06 #10

P: n/a
"lovecreatesbeauty" <lo***************@gmail.com> wrote in message
news:11**********************@u72g2000cwu.googlegr oups.com...
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.


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...n+algorithm%22
lovecreatesbeauty

Jun 20 '06 #11

P: n/a
lovecreatesbeauty wrote:
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.


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.

--
"I don't know where bin Laden is. I have no idea and really
don't care. It's not that important." - G.W. Bush, 2002-03-13
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th." - George Walker Bush 2003-09-17
Jun 20 '06 #12

P: n/a
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;
}
--
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)
Jun 20 '06 #13

P: n/a

CBFalconer wrote:
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[i];
p[i] = 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[i]);
}

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

Jun 20 '06 #14

P: n/a

Richard Heathfield wrote:
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

Jun 20 '06 #15

P: n/a
lovecreatesbeauty said:

Richard Heathfield wrote:
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


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

--
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)
Jun 20 '06 #16

P: n/a

Richard Heathfield wrote:
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

Jun 20 '06 #17

P: n/a
lovecreatesbeauty said:

Richard Heathfield wrote:
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.


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
--
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)
Jun 20 '06 #18

P: n/a
Richard Heathfield <in*****@invalid.invalid> writes:
[...]
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>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Jun 20 '06 #19

P: n/a
Richard Heathfield wrote:
lovecreatesbeauty said:
Richard Heathfield wrote:
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


(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

--
"I don't know where bin Laden is. I have no idea and really
don't care. It's not that important." - G.W. Bush, 2002-03-13
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th." - George Walker Bush 2003-09-17
Jun 20 '06 #20

P: n/a

CBFalconer wrote:
That was the script component I mentioned in my post. The OP has
Hi, it was not the OP but me has responded to your posts. :)
obviously not bothered to look up my posting of the code yet. The
script part was:

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


I would like to see how those "unique" are programmed in your C code
but not just in a dummy shell script. :) Yes, if you have done it in C
code already. To be frank, the permutation algorithm is a little
difficult to me. If I was Newton, I can give a perfect solution quickly
on that. I think so.

lovecreatesbeauty

Jun 21 '06 #21

P: n/a
CBFalconer wrote:
[1] c:\dnld\scratch>jumble abcde
string="abcde", max=120, len=5 <snip>

No script here, right?
[1] c:\dnld\scratch>jumble abcdd
string="abcdd", max=120, len=5 <snip> Hint: both a c program and a script are involved.


Script is used here, right? Script has its short, it brings your the
flaw in the result of your program. I mean the "max=120" is not
suitable for the corresponding situation. There will be no such a flaw
if it's programmed in C code totally.

lovecreatesbeauty

--
A baby calf is not afraid of tigers - Saying

Jun 21 '06 #22

P: n/a
Groovy hepcat lovecreatesbeauty was jivin' on 20 Jun 2006 18:56:19
-0700 in comp.lang.c.
Re: permutation generation's a cool scene! Dig it!
CBFalconer wrote:
That was the script component I mentioned in my post. The OP has


Hi, it was not the OP but me has responded to your posts. :)
obviously not bothered to look up my posting of the code yet. The
script part was:

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


I would like to see how those "unique" are programmed in your C code
but not just in a dummy shell script. :) Yes, if you have done it in C


It's simple, really. It surprised me how simple it was when I
figured it out. All you do is sort the substring first; then when
rotating, if the same character comes into the initial position of the
substring as was there previously, you just keep rotating.
To demonstrate this, take the (sorted) string "abbc". Now, on first
iteration of the critical loop the permutation is "abbc". Then you
rotate the string, and the second iteration yeilds "bbca". Rotate
again, and we get "bcab". But, since this string begins with the same
letter as the previous one, we skip this one and keep revolving. So we
next get "cabb".
I hope that makes sense.

--

Dig the even newer still, yet more improved, sig!

http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
Jun 21 '06 #23

P: n/a
lovecreatesbeauty wrote:
CBFalconer wrote:
That was the script component I mentioned in my post. The OP has


Hi, it was not the OP but me has responded to your posts. :)
obviously not bothered to look up my posting of the code yet. The
script part was:

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


I would like to see how those "unique" are programmed in your C code
but not just in a dummy shell script. :) Yes, if you have done it in C
code already. To be frank, the permutation algorithm is a little
difficult to me. If I was Newton, I can give a perfect solution quickly
on that. I think so.


They are NOT in my C code, why should they be? The point of the
script is to simply run existing tools so that the combination
produces the desired result.

--
"I don't know where bin Laden is. I have no idea and really
don't care. It's not that important." - G.W. Bush, 2002-03-13
"No, we've had no evidence that Saddam Hussein was involved
with September the 11th." - George Walker Bush 2003-09-17
Jun 21 '06 #24

P: n/a
"lovecreatesbeauty" <lo***************@gmail.com> writes:
To be frank, the permutation algorithm is a little difficult to
me.


An alternative approach would be:

size = strlen(argv[1]);
strcpy(permuted, argv[1]);
do {
printf("%s\n", permuted);
i = size-1;
while (i > 0 && permuted[i] <= permuted[i-1]) {
--i;
}
if (i > 0) {
j = size-1;
while (permuted[j] <= permuted[i-1]) {
--j;
}
tmp = permuted[j];
permuted[j] = permuted[i-1];
permuted[i-1] = tmp;
}
j = size-1;
while (i < j) {
tmp = permuted[j];
permuted[j] = permuted[i];
permuted[i] = tmp;
++i;
--j;
}
} while (strcmp(permuted, argv[1]) != 0);

and there is no need to filter out duplicates.

Yours,

--
Jean-Marc
Jun 21 '06 #25

P: n/a
lovecreatesbeauty said:

CBFalconer wrote:
That was the script component I mentioned in my post. The OP has


Hi, it was not the OP but me has responded to your posts. :)
obviously not bothered to look up my posting of the code yet. The
script part was:

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


I would like to see how those "unique" are programmed in your C code


I explained that before. All you have to do is pour them into some kind of
container that keeps its contents sorted, such as a binary search tree or a
hash table. This will trivially enable you to eliminate duplicates.

--
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)
Jun 21 '06 #26

P: n/a
Peter Shaggy Haywood said:
It's simple, really. It surprised me how simple it was when I
figured it out. All you do is sort the substring first; then when
rotating, if the same character comes into the initial position of the
substring as was there previously, you just keep rotating.


Neat. I hadn't thought of that. It certainly makes anagram generators more
practical. I hope you'll accept this biscuit -> O <- for Ronny as a token
of thanks.

--
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)
Jun 21 '06 #27

P: n/a
Jean-Marc Bourguet wrote:
An alternative approach would be:

<snip>

I want to keep this interface in my coming perm() function, like:

int perm(char *dest[], const char *src)

I've seen lots doesn't use such a interface and use recursive calls
like the one provided by Richard in this thread.

...
Permute(Perm, n, unchanged + 1);
...

Thank you. I'll study your code and want to get inspired from it.

lovecreatesbeauty

Jun 21 '06 #28

This discussion thread is closed

Replies have been disabled for this discussion.