генерація перестановок
Перестановка - це комбінація елементів з N різних елементів взятих в певному порядку. В перестановці важливий порядок проходження елементів, і в перестановці повинні бути задіяні всі N елементів.
Завдання. Знайти всі можливі перестановки для послідовності чисел 1, 2, 3.
Існують наступні перестановки:
Перестановки без повторень
Кількість перестановок для N різних елементів складає N !. дійсно:
- на перше місце може бути поміщений будь-який з N елементів (всього варіантів N),
- на другу позицію може бути поміщений будь-який з решти (N-1) елементів (разом варіантів N · (N-1)),
- якщо продовжити цю послідовність для всіх N місць, то отримаємо: N · (N-1) · (N-2) ·. · 1. тобто всього N! перестановок.
Розглянемо задачу отримання всіх перестановок чисел 1. N (тобто послідовності довжини N), де кожне з чисел входить рівно по 1 разу. Існує безліч варіантів порядку отримання перестановок. Однак найбільш часто вирішується завдання створення перестановок в лексикографічному порядку (див. Приклад вище). При цьому всі перестановки упорядковано спочатку по першому числу, потім по другому і т.д. в порядку збільшення. Таким чином, першою буде перестановка 1 2. N. а останньою - N N-1. 1.
Розглянемо алгоритм вирішення задачі. Дана вихідна послідовність чисел. Для отримання кожної наступної перестановки необхідно виконати наступні кроки:
Таким чином ми отримаємо нову послідовність, яка буде розглядатися в якості вихідної на наступному кроці.
Реалізація на С ++
#include
using namespace std;
void swap (int * a, int i, int j)
int s = a [i];
a [i] = a [j];
a [j] = s;
>
bool NextSet (int * a, int n)
int j = n - 2;
while (j! = -1 a [j]> = a [j + 1]) j--;
if (j == -1)
return false; // більше перестановок немає
int k = n - 1;
while (a [j]> = a [k]) k--;
swap (a, j, k);
int l = j + 1, r = n - 1; // сортуємо решту послідовності
while (l
return true;
>
void Print (int * a, int n) // висновок перестановки
static int num = 1; // номер перестановки
cout.width (3); // ширина поля виведення номера перестановки
cout <
int main ()
int n, * a;
cout <<"N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i
Print (a, n);
while (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
>
Перестановки з повтореннями
На особливу увагу заслуговує завдання генерації перестановок N елементів в разі якщо елементи послідовності можуть повторюватися. Припустимо, вихідна послідовність складається з елементів n1. n2. nk. де елемент n1 повторюється r1 раз, n2 повторюється r2 раз і т.д. При цьому n1 + n2 +. + Nk = N. Якщо ми будемо вважати все n1 + n2 +. + Nk елементів перестановки з повтореннями різними, то всього різних варіантів перестановок (n1 + n2 +. + Nk) !. Однак серед цих перестановок не всі різні. Справді, все r1 елементів n1 ми можемо переставляти місцями один з одним, і від цього перестановка не зміниться. Точно так же, можемо переставляти елементи n2. n3 і т. д. В результаті маємо r1! варіантів запису однієї і тієї ж перестановки з різним розташуванням повторюваних елементів n1. Таким чином, будь-яка перестановка може бути записана r1! · R2! ·. · Rk! способами. Отже, число різних перестановок з повтореннями одно
Для генерації перестановок з повтореннями можна використовувати алгоритм генерації перестановок без повторень, наведений вище. Введемо повторюваний елемент в масив a. Нижче наведено код програми для генерації перестановок з повтореннями (змінений тільки код функції main ()).
#include
using namespace std;
void swap (int * a, int i, int j)
int s = a [i];
a [i] = a [j];
a [j] = s;
>
bool NextSet (int * a, int n)
int j = n - 2;
while (j! = -1 a [j]> = a [j + 1]) j--;
if (j == -1)
return false; // більше перестановок немає
int k = n - 1;
while (a [j]> = a [k]) k--;
swap (a, j, k);
int l = j + 1, r = n - 1; // сортуємо решту послідовності
while (l
return true;
>
void Print (int * a, int n) // висновок перестановки
static int num = 1; // номер перестановки
cout.width (3); // ширина поля виведення номера перестановки
cout <
int main ()
int n, * a;
cout <<"N = " ;
cin >> n;
a = new int [n];
for (int i = 0; i
a [1] = 1; // повторюваний елемент
Print (a, n);
while (NextSet (a, n))
Print (a, n);
cin.get (); cin.get ();
return 0;
>
Результат роботи наведеного вище алгоритму:
