Richard Heathfield's TSP permutation algorithm
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 
Re: Richard Heathfield's TSP permutation algorithm
whitehatmiracle@gmail.com 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 bruteforcer, I suggest you hack it to accept a function that will be called whenever a permutation is found.  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) 
Re: Richard Heathfield's TSP permutation algorithm
What does inner outer and unchanged do?

Re: Richard Heathfield's TSP permutation algorithm
whitehatmiracle@gmail.com 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 righthand side to the lefthand 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 righthand side, and incorporating the lefthand 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 righthand side to the lefthand 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 righthand side, and incorporating the lefthand 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 righthand side to the lefthand 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 righthand side, and incorporating the lefthand 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 righthand side to the lefthand 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 righthand side, and incorporating the lefthand side, ***unchanged***, into the final result. But since each righthand 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.  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) 
Re: Richard Heathfield's TSP permutation algorithm
Richard Heathfield wrote:
> whitehatmiracle@gmail.com 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 righthand side to the lefthand 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 righthand side, and incorporating > the lefthand 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 righthand side to the lefthand 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 righthand side, and incorporating the > lefthand 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 righthand side to the lefthand 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 righthand side, and incorporating > the lefthand 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 righthand side to the lefthand 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 righthand side, and > incorporating the lefthand side, ***unchanged***, into the final > result. But since each righthand 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[i]; wd[i] = 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, lgh1, ix+1, n1, outstring); trade(wd, i); /* restore the wd string */ } } /* jumble */  "The most amazing achievement of the computer software industry is its continuing cancellation of the steady and staggering gains made by the computer hardware industry..."  Petroski  Posted via a free Usenet account from http://www.teranews.com 
Re: Richard Heathfield's TSP permutation algorithm
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...... 
Re: Richard Heathfield's TSP permutation algorithm
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); } 
Re: Richard Heathfield's TSP permutation algorithm
whitehatmiracle@gmail.com 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.  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) 
Re: Richard Heathfield's TSP permutation algorithm
So actually what would be the appropriate name for outer and inner?

Re: Richard Heathfield's TSP permutation algorithm
whitehatmiracle@gmail.com 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.  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) 
All times are GMT. The time now is 07:59 PM. 
Powered by vBulletin®. Copyright ©2000  2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.