permutation generation
onkar
ex : for n= 3, and basic string = abc
bca
cab
bac
cab
....
..
.
pemo
Go see Google Groups - search comp.lang.c for 'permutations' - finds 250+
results
--
==============
Not a pedant
==============
Richard Heathfield
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)
spi...@gmail.com
onkar wrote:
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[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
Richard Heathfield
<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?
Bill Pursell
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!
>
>
> 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
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
> > $ 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
Peter Nilsson
> 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.lang.c/msg/98c0260bb56e83f2
--
Peter
Dann Corbit
news:1150768355.3...@u72g2000cwu.googlegroups.com...
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=%22permutation+algorithm%22
> lovecreatesbeauty
>
CBFalconer
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
Richard Heathfield
> $ 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
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
lovecreatesbeauty
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.)
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
>
> 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.
lovecreatesbeauty
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
Richard Heathfield
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>
--
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.
CBFalconer
> 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
lovecreatesbeauty
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
lovecreatesbeauty
> [1] c:\dnld\scratch>jumble abcde
> string="abcde", max=120, len=5
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
Peter Shaggy Haywood
-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"?
CBFalconer
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.
Jean-Marc Bourguet
> 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
Richard Heathfield
>
> 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
> 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.
lovecreatesbeauty
> An alternative approach would be:
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