Генерация перестановок из n элементов с минимальными изменениями.
Генерация перестановок из n элементов в лексикографическом порядке.
Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все перестановки элементов множества Z.
Начинаем с перестановки {1,2,3,…n}. По предыдущей перестановке {x1,x2,…,xn} будем строить следующую за ней в лексикографическом порядке. У нашей перестановки можно увеличить i-й член, не меняя предыдущих, если он меньше какого-либо из следующих членов (членов с номерами больше i). Таким образом: просматривая нашу перестановку справа налево, находим самую первую позицию i, т.ч. xi<xi+1. Если такой позиции нет, то заканчиваем работу. После этого xi нужно увеличить наименьшим возможным способом. Для этого, просматривая элементы перестановки от xi слева направо, ищем наименьший из элементов xj, т.ч. xi<xj.Меняем местами xi с xj. Теперь элементы справа от xi образуют убывающую последовательность. Переписываем элементы от xi+1 до xn в обратном порядке.
Следующая программа реализует данный алгоритм:
#include<stdio.h>
#include<conio.h>
#define n 4
int x[n];
main(){
int i,j,tmp,min,nmi;
for(i=0;i<n;i++) //Формируем начальную перестановку
x[i]=i+1;
while(1){
for(i=0;i<n;i++) //Печатаем очередную перестановку
printf("%d ",x[i]);
printf("\n");
for(i=n-2;i>=0 && x[i+1]<x[i];i--) //Ищем первый справа xi, т.ч. xi < xi+1
;
if(i==-1) break; //Если не нашли, заканчиваем работу.
min=100;nmi=i; //Ищем справа от xi наименьший xj, т.ч. xi < xj.
for(j=i+1;j<n;j++)
if(x[j]>x[i] && x[j]<min){
min=x[j];nmi=j;
}
x[nmi]=x[i];x[i]=min; //Меняем xi с xj.
for(j=i+1;j<=(i+n)/2;j++){ //Переписываем элементы справа от xi
tmp=x[j];x[j]=x[i+n-j];x[i+n-j]=tmp;//в обратном порядке.
}
}
getch();
return 0;
}
Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все перестановки элементов множества Z. При этом необходимо, чтобы каждая следующая перестановка получалась из предыдущей при помощи одной транспозиции (перестановки) двух соседних элементов. Например, при n = 3 допустим такой порядок: 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3 -> 1 3 2 -> 3 1 2.
Идея решения взята из [1]. Рассмотрим множество последовательностей y0, y1,…, yn-1 целых неотрицательных чисел, у которых y0<=0, y1<=1,…, yn-1<=n-1. Установим взаимно однозначное соответствие между множеством перестановок из n элементов и множеством таких последовательностей. Именно, каждой перестановке поставим в соответствие последовательность y0, y1,…, yn-1, где yi - количество чисел, меньших i+1 и стоящих левее i+1 в этой перестановке. В качестве примера рассмотрим случай n=3.| Перестановка | Последовательность | ||
| y0 | y1 | y2 | |
| 321 | 0 | 0 | 0 |
| 231 | 0 | 0 | 1 |
| 213 | 0 | 0 | 2 |
| 123 | 0 | 1 | 2 |
| 132 | 0 | 1 | 1 |
| 312 | 0 | 1 | 0 |
Теперь вспомним решение задачи о генерации всех последовательностей длины n из чисел 0,1…k-1 с минимальными изменениями. Заменим прямоугольную доску доской в форме лестницы (пронумеруем вертикали от 0 до n-1, высота i-ой вертикали равна i). Двигая шашки по тем же правилам, мы сгенерируем все возможные последовательности y. Параллельно с изменением yбудем корректировать перестановку. Для этого можно искать в ней число i+1, но это требует лишних действий. Поэтому мы будем для получения i+1 в массиве inv_x хранить перестановку, обратную нашей, изменяя ее по мере необходимости.
Первой будет сгенерирована перестановка n,n-1,…1. Ей соответствует последовательность yиз одних нулей.
Программа, реализующая данный алгоритм, выглядит так:
#include<stdio.h>
#include<conio.h>
#define n 4
int y[n], x[n+1], inv_x[n+1], d[n];
int nelzia(int i){
if((y[i]==i && d[i]==1) || (y[i]==0 && d[i]==-1)) //Функция возвращает 1,если i – й
return 1; //шашкой нельзя пойти,
else return 0; //и 0, если можно.
}
void printfX(void){ //Функция печатает очередную
for(int i=1;i<=n;i++) //перестановку x.
printf("%d ",x[i]);
printf("\n");
}
main(){
int i,j,pos1,pos2,val1,val2,tmp;
for(i=0;i<n;i++){ //Заносим начальные значения.
x[i+1]=n-i;
inv_x[i+1]=n-i;
d[i]=1;
y[i]=0;
}
while(1){
printfX();
for(i=n-1;i>=0 && nelzia(i);i--) //Ищем самую правую шашку,
; //у которой есть ход.
if(i==-1) break; //Если не нашли, то конец.
y[i]=y[i]+d[i]; //Генерируем новый y.
pos1 = inv_x[i+1]; //pos1 – номер элемента i+1 в перестановке
val1 = i+1; //pos2 – номер соседа, с которым будем
pos2 = pos1 + d[i]; //его менять.
val2 = x[pos2];
tmp = x[pos1]; //Меняем i+1 с соседом
x[pos1] = x[pos2]; //в перестановке x и в обратной.
x[pos2] = tmp;
tmp = inv_x[val1];
inv_x[val1] = inv_x[val2];
inv_x[val2] = tmp;
for(j=i+1;j<n;j++) //Меняем направление движения
d[j]=-d[j]; //шашек, которые уперлись в край доски
} //правее нашей шашки.
getch();
return 0;
}