Richard Heathfield's TSP permutation algorithm

[whitehatmiracle]

Dear Sir I couldnt quite figure out wat your permute function does
exactly... could you please throw some light on it?
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;

}

Thanking you
The whitehat

 

[Richard Heathfield]

(e-mail address removed) said:

Dear Sir I couldnt quite figure out wat your permute function does
exactly... could you please throw some light on it?

It just permutes an array. If you want to turn it into a brute-forcer, I
suggest you hack it to accept a function that will be called whenever a
permutation is found.

 

[whitehatmiracle]

What does inner outer and unchanged do?

 

[Richard Heathfield]

(e-mail address removed) said:

What does inner outer and unchanged do?

Partition the array into two parts, an empty part, and the part you want to
permute.

| ABCDE

Move each element on the right-hand side to the left-hand side, in turn.

A | BCDE
B | CDEA
C | DEAB
D | EABC
E | ABCD

All you're really doing is rotating the array, yes?

For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.

Take A | BCDE, for example. We have 1 unchanged element, which will prefix
each solution, and an array, BCDE. We can solve this problem by recursing.
How? Well, like this...

Move each element on the right-hand side to the left-hand side, in turn.

AB | CDE
AC | DEB
AD | EBC
AE | BCD

All you're really doing is rotating the BCDE part of the array, yes?

For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.

Take AB | CDE, for example. We have 2 unchanged elements, which will prefix
each solution, and an array, CDE. We can solve this problem by recursing.
How? Well, like this...

Move each element on the right-hand side to the left-hand side, in turn.

ABC | DE
ABD | EC
ABE | CD

All you're really doing is rotating the CDE part of the array, yes?

For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result.

Take ABC | DE, for example. We have 3 unchanged elements, which will prefix
each solution, and an array, DE. We can solve this problem by recursing.
How? Well, like this...

Move each element on the right-hand side to the left-hand side, in turn.

ABCD | E
ABCE | D

All you're really doing is rotating the DE part of the array, yes?

For each of those partitioned array arrangements, we now have to solve the
problem of permuting the right-hand side, and incorporating the left-hand
side, ***unchanged***, into the final result. But since each right-hand
side only has 1 element therein, there is only one permutation.

So for each of them we just display the result. ABCDE, and ABCED.

Then we drop out of this recursion, and continue with the next, and so on
until everything is done.

 

[CBFalconer]

(e-mail address removed) said:


Partition the array into two parts, an empty part, and the part
you want to permute.

| ABCDE

Move each element on the right-hand side to the left-hand side,
in turn.

A | BCDE
B | CDEA
C | DEAB
D | EABC
E | ABCD

All you're really doing is rotating the array, yes?

For each of those partitioned array arrangements, we now have to
solve the problem of permuting the right-hand side, and incorporating
the left-hand side, ***unchanged***, into the final result.

Take A | BCDE, for example. We have 1 unchanged element, which will
prefix each solution, and an array, BCDE. We can solve this problem
by recursing. How? Well, like this...

Move each element on the right-hand side to the left-hand side,
in turn.

AB | CDE
AC | DEB
AD | EBC
AE | BCD

All you're really doing is rotating the BCDE part of the array, yes?

For each of those partitioned array arrangements, we now have to solve
the problem of permuting the right-hand side, and incorporating the
left-hand side, ***unchanged***, into the final result.

Take AB | CDE, for example. We have 2 unchanged elements, which will
prefix each solution, and an array, CDE. We can solve this problem
by recursing. How? Well, like this...

Move each element on the right-hand side to the left-hand side, in
turn.

ABC | DE
ABD | EC
ABE | CD

All you're really doing is rotating the CDE part of the array, yes?

For each of those partitioned array arrangements, we now have to
solve the problem of permuting the right-hand side, and incorporating
the left-hand side, ***unchanged***, into the final result.

Take ABC | DE, for example. We have 3 unchanged elements, which will
prefix each solution, and an array, DE. We can solve this problem by
recursing. How? Well, like this...

Move each element on the right-hand side to the left-hand side, in
turn.

ABCD | E
ABCE | D

All you're really doing is rotating the DE part of the array, yes?

For each of those partitioned array arrangements, we now have to
solve the problem of permuting the right-hand side, and
incorporating the left-hand side, ***unchanged***, into the final
result. But since each right-hand side only has 1 element therein,
there is only one permutation.

So for each of them we just display the result. ABCDE, and ABCED.

Then we drop out of this recursion, and continue with the next,
and so on until everything is done.

And that very nice description applies equally to my 'jumble'
routine, which I published here earlier as a complete program.
Jumble also allows you to suppress any output past a preselected
length value.

Richards description, and my lack of one, illustrates why I do not
make a good teacher. I am repeating my actual heart code for
illustration below:

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd;
wd = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

 

[whitehatmiracle]

WOW
Thanx a millions to Mr Richard Heathfield and to Mr CBFalconer
Now both your algorithms are clear, and even the ideas are clearer.

Thanx once again......

 

[whitehatmiracle]

Just one last clarification:

for
A | BCDE
B | CDEA
inner is the right hand side of the bar |?
and outer is it the left hand side of the | bar?

The external most for loop does it permute only the first letter of the
combination??


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);
}

 

[Richard Heathfield]

(e-mail address removed) said:

Just one last clarification:

for
A | BCDE
B | CDEA
inner is the right hand side of the bar |?
and outer is it the left hand side of the | bar?

No. You leave everything to the left of the bar alone.

The external most for loop does it permute only the first letter of the
combination??

Nothing special about it at all. It just rotates the array and then recurses
to permute each rotation in turn.

if(unchanged < n)

Have we finished yet? No? Okay, let's rotate the array...

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

This bit changes, say, BCDE into EBCD

Permute(Perm,
n,
unchanged + 1);

This bit submits AEBCD to recursion.

for(inner = unchanged; inner < outer; inner++)
{
Perm[inner] = Perm[inner + 1];
}
Perm[outer] = temp;

And this bit jiggles the array back into the right order so that the next
recursion level up from here works properly.

 

[whitehatmiracle]

So actually what would be the appropriate name for outer and inner?

 

[Richard Heathfield]

(e-mail address removed) said:

So actually what would be the appropriate name for outer and inner?

In the absence of contextual information to the contrary, the most
appropriate name for outer is outer.

In the absence of contextual information to the contrary, the most
appropriate name for inner is inner.

 

[Keith Thompson]

So actually what would be the appropriate name for outer and inner?

Please provide context. See <http://cfaj.freeshell.org/google/>.
(The bug in Google Groups has been corrected, so it's even easier to
get this right.)

 

[CBFalconer]

(e-mail address removed) said:


In the absence of contextual information to the contrary, the most
appropriate name for outer is outer.

In the absence of contextual information to the contrary, the most
appropriate name for inner is inner.

This is probably a discussion of naval strategy. In the UK, direct
the questions to the Admiralty. Try the First Sea Lord. In the
US, try the Department of the Navy.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[whitehatmiracle]

Sorry for the netiquette:
I meantwhat would be the approproate name for inner and outer?

This is probably a discussion of naval strategy. In the UK, direct
the questions to the Admiralty. Try the First Sea Lord. In the
US, try the Department of the Navy.

OMG Hahahahaaa nice one