[перестановка]

From

Igor Filimonov (2:5020/2647.8)

To

Iwan Kroot

Date

2002-05-15T16:03:11Z

Area

RU.ALGORITHMS

     Ну вот, опять Я!

 Iwan Kroot wrote for All:

 IK>         Дано n чисел, необходимо вывести все возможные варианты
 IK> перестановки. Мне нужен самый простой алгоритм.

    Вот, два варианта, оба в виде C/C++ кода, но
алгоритм выделить, думаю, несложно
   Первый вариант, все обычные перестановки от 1 до N:
>===============
#include <stdio.h>
#define      N    4   //  число элементов
#define  NFACT    24  //  N!
void main(void){
  int a,c,t,m[8];
  long n;
  for(n=0;n<NFACT;n++) {
     for(a=0;a<N;a++) m[a]=a;
     for(a=0,c=n; a<N-1; a++)
    {t=m[a]; m[a]=m[a+c%(N-a)]; m[a+c%(N-a)]=t; c/=(N-a); }
     for(a=0; a<N; a++) printf(" %d",m[a]+1);
     printf("\n");
    }
}
>===============
    Второй вариант - если нужно учитывать ещё и
дублирующиеся элементы. Эта функция в некоторой степени
является аналогом соответствующей функции из C++ STL
///////////////////
template <class T> int my_next_permutation(T *mass, int sz)
{
int a,b,c,d;
T ttt, tc;

//   Ищем такой последний из элементов, что его значение
// меньше последующего. 
for(a=sz-2;  a>=0 && mass[a]>=mass[a+1];  a--);

//   Массив отсортирован, дальше переставлять уже некуда.
if(a<0) return 0;

//   Записываем в c номер найденного элемента, а в tc -
// значение этого элемента.
c=a;
tc=mass[a];

//   Ищем среди элементов, следующих за c, элемент,
// наименьший по значению среди больших чем tc. Используем,
// что хвост отсортирован по убыванию. Также помним, что
// такой элемент обязательно существует.
for(a=sz-1; mass[a]<=tc;  a--);

//  меняем местами найденный элемент и элемент c
mass[c]=mass[a];
mass[a]=tc;

//  Меняем упорядоченность хвоста с убывания на возрастание
for(b=c+1, d=sz-1;  b<d;  b++,d--)
   { ttt=mass[b];  mass[b]=mass[d]; mass[d]=ttt; }

//  Перестановка успешно произведена.
return 1;
}
///////////////////


               With respect,  Игорь Филимонов.

PGP key fingerprint:  28 B2 CB 8A 85 F6 82 1A    FC 8E BE B0 91 61 C9 68

... Лучше жуpавль в pуках, чем синица в небе.
---
 * Origin: [skip] (2:5020/2647.8)