Алгоритм перестановок выполнен следующим образом.

#include<iostream.h>
#include<algorithm.h>
#include<conio.h>
using namespace std;
int main()
{
int a[100];
int m, i;
cout<<"Input m<100 ";
cin>>m;
        for (i=0; i<m; i++)
        {
        a[i]=i+1;
        cout<<a[i]<<" ";
        }
cout<<"\n";
while (next_permutation(a,a+m))
        {
        for (i=0; i<m; i++)
        cout <<a[i] <<" ";
        cout << endl;
        }
getch();
}

Подскажите вариант реализации без использования обобщённых функций.

Здравствуйте, fanpilot, Вы писали:

F>Подскажите вариант реализации без использования обобщённых функций.

Вариант без обобщённых функций состоит в том, чтобы скопипастить определение next_permutation (и всё, от чего он зависит) из <algorithm> и убрать оттуда слово template

А сама идея алгоритма (Д.Кнута, кстати) проста, как сибирский валенок — или как wellington boot.
Пусть перед очередной итерацией наш массив заполнен так: [q,w,e,...,r,M,Z,Y,X,...,C,B,A]
То есть, существует нестрого-убывающий хвост Z >= Y >= ... >= B >= A, отделённый от произвольной головы q,w,e... элементом M, строго меньшим Z.
(Был бы M==Z, — принадлежал бы нестрого-убывающему хвосту M>=Z>=...)

Какая перестановка будет следующей в порядке лексикографического возрастания (как если бы мы переставляли буквы в слове)?
Очевидно, что любые варианты вида [q,w,e,...,r,M]+permute{Z,Y,X,...,C,B,A} — окажутся меньше-или-равны текущему — т.к. голова у них совпадает, а любая перестановка невозрастающего подмассива (хвоста) даст меньший-или-равный подмассив.
Также очевидно, что нужно сохранить как можно более длинную голову неизменной. То есть, вовлечь в перестановку только элемент M.
Получаем [q,w,e,...,r]+minimal_permutation{M,Z,Y,X,...,C,B,A}
Наименьшая перестановка — это массив, отсортированный по возрастанию. То есть, [A,B,C,...,M,...,X,Y,Z]

next_permutation останавливается, когда весь массив оказывается отсортирован по убыванию.

Отсюда план работ
0) если длина массива 0 или 1 — то всё.

1) находим позицию im элемента M, начиная с len-2 и убывая, так, что arr[im]<arr[im+1].
Если поиск закончился неуспешно (im<0) — то всё.

2) переворачиваем подмассив arr[im+1]..arr[len-1]
(это требует аккуратности в работе с индексами)

3) находим положение ins для вставки arr[im] в arr[im+1..len-1], так, что arr[ins]>arr[im]
4) вставляем элемент arr[im] на это место, сдвигая arr[im+1..ins] влево на одну позицию
5) и говорим "не всё!"

Закодировать алгоритм — упражнение для первокурсника %)

Здравствуйте, Кодт, Вы писали:

К>Также очевидно, что нужно сохранить как можно более длинную голову неизменной. То есть, вовлечь в перестановку только элемент M.
К>Получаем [q,w,e,...,r]+minimal_permutation{M,Z,Y,X,...,C,B,A}
К>Наименьшая перестановка — это массив, отсортированный по возрастанию. То есть, [A,B,C,...,M,...,X,Y,Z]

при таком подходе алгоритм зациклится скорее всего
обычно next_permutation выдает элементы по возрастанию, то есть a < next_permutation(a)

имхо надо в таком духе:

Получаем [q,w,e,...,r]+minimal_next_permutation{M,Z,Y,X,...,C,B,A}
Наименьшая следующая перестановка — это замена буквы M на след. по возрастанию букву и инвертация отсортированного хвоста, то есть [N,A,B,C,...M,...Y,Z]

Здравствуйте, uzhas, Вы писали:

U>имхо надо в таком духе:

U>Получаем [q,w,e,...,r]+minimal_next_permutation{M,Z,Y,X,...,C,B,A}
U>Наименьшая следующая перестановка — это замена буквы M на след. по возрастанию букву и инвертация отсортированного хвоста, то есть [N,A,B,C,...M,...Y,Z]

Ай, точно! Мой вариант зациклится, твой правильный. Именно minimal_next_permutation.

Здравствуйте, fanpilot, Вы писали:

F>Подскажите вариант реализации без использования обобщённых функций.

Как вариант неплохой рекурсивный алгоритм

void HeapPermute(int v[], int n)
{
   if (n == 1) 
   {
      print(v);
   }
   else 
   {
      for (int i = 0; i < n; i++) 
      {
         HeapPermute(v, n-1);
         if (n % 2 == 1)  // if n is odd
            swap(v[0], v[n-1]);
         else            // if n is even
            swap(v[i], v[n-1]);
      }
   }
}

Здравствуйте, AndrewJD, Вы писали:

AJD>Здравствуйте, fanpilot, Вы писали:

F>>Подскажите вариант реализации без использования обобщённых функций.

AJD>Как вариант неплохой рекурсивный алгоритм

Единственная проблема — он переставляет элементы, невзирая на их эквивалентность — и выдаёт ровно n! строк.
Если в массиве есть одинаковые элементы, то на выходе будут встречаться одинаковые массивы.
В отличие от алгоритма Кнута и любых других алгоритмов, следящих за этим делом.

Кстати, если массив состоит из k одинаковых значений и n-k других одинаковых значений, то мы должны получить C(n,k) сочетаний.
И алгоритм Кнута это отлично делает; причём его можно упростить, заточив под тот факт, что в массиве ровно две величины встречаются.
(Я когда-то даже выразил это через регексп — на форуме есть, искать сейчас не буду).

Здравствуйте, AndrewJD, Вы писали:

AJD>Как вариант неплохой рекурсивный алгоритм
вариант в действии: http://ideone.com/7C44o

Здравствуйте, uzhas, Вы писали:

U>Здравствуйте, AndrewJD, Вы писали:

AJD>>Как вариант неплохой рекурсивный алгоритм
U>вариант в действии: http://ideone.com/7C44o

вот так по аккуратнее вывод будет

void print(int v[])
{
  for (size_t i = 0; i < v_size; ++i)
  {
    printf(",%d" + int(i == 0), v[i]);
  }
  printf("\n");
  ++count;
}

Здравствуйте, fanpilot, Вы писали:

F>Алгоритм перестановок выполнен следующим образом.


F>

F>#include<iostream.h>
F>#include<algorithm.h>
F>#include<conio.h>
F>using namespace std;
F>int main()
F>{
F>int a[100];
F>int m, i;
F>cout<<"Input m<100 ";
cin>>>m;
F>        for (i=0; i<m; i++)
F>        {
F>        a[i]=i+1;
F>        cout<<a[i]<<" ";
F>        }
F>cout<<"\n";
F>while (next_permutation(a,a+m))
F>        {
F>        for (i=0; i<m; i++)
F>        cout <<a[i] <<" ";
F>        cout << endl;
F>        }
F>getch();
F>}
F>

F>Подскажите вариант реализации без использования обобщённых функций.

Любую перестановку можно получить по её номеру.