permutation generation

[lovecreatesbeauty]

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

<snip>

No script here, right?

[1] c:\dnld\scratch>jumble abcdd
string="abcdd", max=120, len=5

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

 

[CBFalconer]

Hi, it was not the OP but me has responded to your posts.


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.

 

[Peter Shaggy Haywood]

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!

Hi, it was not the OP but me has responded to your posts.


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

 

[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 <= 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;
permuted = tmp;
++i;
--j;
}
} while (strcmp(permuted, argv[1]) != 0);

and there is no need to filter out duplicates.

Yours,

 

[Richard Heathfield]

lovecreatesbeauty said:

Hi, it was not the OP but me has responded to your posts.


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]

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.

 

[lovecreatesbeauty]

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