Недавно была задача написать программу для вычисления детерминанта матрицы. Для этого мне нужно было решить еще парочку задач одна из которых была построение всех перестановок. Алгоритм достаточно прост для применения, и, не смотря на то, что она предназначена для цифр, ее также можно применить для символов (составив массив из символов).
Алгоритм перестановок
Будем рассматривать случай когда цифры от 1 до n лежат в массиве в порядке возрастания, в противном случае можно просто переставить с помощью переставить.
Предположим имеем числа 1234. Очевидно, что количество перестановок равно 4!=24. Если мы начнем просто переставлять всякие два элемента то будет огромное кол.-во повторений, которых не избежать.
Для этого сделаем так, чтобы каждая новая перестановка поэлементно была больше предыдущего. К примеру для 1234 следующий будет 1243 и так далее.
Алгоритм
1. Выберем число начиная с конца, элемент где нарушается порядок убывания. То есть для 12345 выберем 4, а для 12354 выберем 3 (точнее индекс i где а[i]=3). Назначим индекс этого элемента m.
2. Выберем наименьшее число после m-ой. Например 12354 m=2 (начинается с нуля) после 2-ого элемента наименьшее число 4, у которого индекс равен 4 (k=4).
3. Меняем местами m-ый и k-ый элемент.
4. Осталось упорядочить все элементы после m-ого по возрастанию (поскольку они упорядочены по убывания, надо просто повернуть их).
Пример
a[4] = {1,2,3,4}, m=2 (a[m]=3), k=3 (a[k]=4). Меняем местами a[m] и a[k]. Получилось {1,2,4,3} и поскольку после m-ого элемента только один элемент повернуть ничего не нужно.
a[4] = {1,2,4,3}, m=1 (a[m] = 2), k=3 (a[k]=3). Меняем местами a[m] и a[k]. Получилось {1,3,4,2}, перевернем все после m-ого индекса получим {1,3,2,4}. И так далее.
Решение на C++
Функции для использования
#include <iostream> // библиотека ввод/вывод
using namespace std; // именная зона std
int fac(int a) // функция факториала (нужно для подсчета кол.-во перестановок)
{
if(a==1) return 1;
return a*fac(a-1);
}
void swap(int *a,int i,int j) // функция для того, чтобы переставить элементы с индексами i и j в массиве a;
{
int t;
t = a[i];
a[i]=a[j];a[j]=t;
}
int get_m(int *a,int N) // функция выбора m, где m индекс первого с конца элемента,
// с которого нарушается порядок убывания
{
int i;
for(i=N-1; i>=1; i--)
if(a[i]>a[i-1])
return i-1;
return 0; }
int get_k(int *a, int fixed_m, short N) // Найти k, где k индекс наименьшего элемента после m-ого.
{
int temp_index = fixed_m+1;
for (int i=fixed_m+1;i<;N;i++)
if(a[i]<a[temp_index] && a[i]>a[fixed_m]) temp_index=i;
return temp_index;
}
Тело программы
int main()
{
int n, i, j, m,k, temp, kol_vo;
cin >> n; // ввод числа n (длина массива)
kol_vo = fac(n); // кол.-во перестановок
short *c = new short[n]; // массив для хранения перестановок
for(i=0;i<n;i++) c[i]=i+1; // заполнение от 1 до n
for(i = 0; i<kol_vo;i++)
{
for(j=0;j<n;j++)cout << c[j] << " "; // вывод нынешнюю перестановку на экарн
cout << endl; // новая строка
m = get_m(c, n); // выбор m
k=get_k(c,m, n); // выбор k
swap(c, m, k); // переставить a[m] и a[k]
if(n-1-m > 1) // если после m-ого есть более 1 элемента
for(short j=0;j<(n-m-1)/2;j++) // перевернуть
{
tt = c[m+1+j];
c[m+1+j]=c[n-1-j];
c[n-1-j]=tt;
}
}
delete [] c; // очистить память
system("pause"); // задержка экрана
return 0; // выход из программы
}
Примечание
Если имеется символьная строка то можно просто создать массив для индексов например index[] и работать с ним так c[index[i]].
Если что-то было не понятно или вы где-то обнаружили ошибку - пишите комментарий.
