Re: коммивояжёр

From

Vladimir Vassilevsky (2:5020/175.2)

To

Oleg Khovayko

Date

2003-01-12T06:36Z

Area

RU.ALGORITHMS

From: "Vladimir Vassilevsky" <vlv@fullnet.net>

Hi Oleg,

Sun Jan 12 2003 06:03, Oleg Khovayko wrote to Ilya Rogov:

 >> Вот про генерацию всех возможных перестановок нерекурсивным 
 OK> способом я как
 >> раз и хотел спросить.

 Нет ничего проще. Вообще-то, за 14+ лет моей практики я  ни разу не 
 встречал задач, для которых была бы нужна рекурсия. 

 Приведите, пожалуйста, пример реальной задачи, которую было бы удобно 
 решать рекурсивно.  

 OK> Так как я пишу на C++, я при необходимости просто зову 
 OK> next_permutation(), и все делается за меня само собою.

 То есть сразу сгенерить произвольно заданную i-тую пермутацию нельзя?
 Плохо :)))))

 OK> Вам же, если вы используете PASCAL, надо самому сгенерить перестановки.

  PASCAL - мертвый язык.

 OK> Вот я нашел в интернете описание генерации перестановок как раз 
 OK> применительно к комми-задаче:

  По третьему разу, генерация любой i-той перестановки, без всяких 
 рекурсий и итераций: 

//(c) VLV
#include <stdio.h>

unsigned int Factorial(unsigned int n)
{
unsigned int i,f = 1;

for(i = 2; i <= n; i++) f *= i;

return f;
}

//-----------------------------------------------
// Generate combination i from n! combinations
// 
//
void GetCombination(unsigned int *c, unsigned int n, unsigned int i)
{
unsigned int j,k,l,m;

for(k = 0; k < n; k++) c[k] = n;

m = 0;
j = Factorial(n);


for(k = n; k >= 1; k--)
 {
 j /= k;
 l = i/j;
 i -= l*j;
 l++;
 do {
    do { 
       if(++m == n) m = 0; 
       } while(c[m] != n);    
    } while(--l);
 c[m] = k-1; 
 }
}

//--------------------------------------------
// 
#define N 5

void main(void)
{
unsigned int i,j,Nfact;
unsigned int c[N];

Nfact = Factorial(N);

for(i=0;i<Nfact;i++)
 {
 GetCombination(c, N, i);
 
 printf("\n");
 for(j=0;j<N;j++) printf(" %u",c[j]); 

 }
printf("\n");
}

"SEX: parity error! Retry, Abort, Ignore?"

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)