Генерация сочетаний в лексикографическом порядке.
Генерация всех последовательностей длины n из чисел 0,1…k-1 с минимальными изменениями.
Требуется перечислить все последовательности длины n из чисел 0,..k-1 в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причем не более, чем на 1.
Идея решения взята из [1]. Рассмотрим прямоугольную доску из n вертикалей и k горизонталей. Пронумеруем горизонтали от 0 до k-1. На каждой вертикали поставим шашку. Таким образом, положения шашек соответствуют последовательностям из чисел 0,..k-1 длины n (s-ый член последовательности соответствует высоте шашки на s-ой горизонтали). На каждой шашке нарисуем стрелочку, которая может быть направлена вверх или вниз. Вначале все шашки поставим на нижнюю (нулевую) горизонталь стрелочкой вверх. Далее двигаем шашки по такому правилу: найдя самую правую шашку, которую можно подвинуть в направлении нарисованной на ней стрелки, двигаем ее на одну клетку в этом направлении, а у всех стоящих правее ее шашек (они уперлись в край) меняем направление стрелки на противоположное. Процесс заканчивается, когда ни одна шашка не может сделать ход. Очевидно, что при таком движении каждая следующая последовательность отличается от предыдущей в одном разряде, причем ровно на единицу. Упр. Доказать, что будут получены все последовательности. Реализуем данный алгоритм. Направления стрелок будем хранить в отдельном массиве d. Стрелке вверх соответствует значение 1, стрелке вниз –значение -1. #include<stdio.h>#include<conio.h>#define n 4#define k 3 int x[n],d[n]; int nelzia(int i){ //Функция возвращает 1, если i-я шашка не может if((x[i]==k-1 && d[i]==1) || //сделать ход, и 0, если может. (x[i]==0 && d[i]==-1)) return 1; else return 0;} main(){ int i,j; for(i=0;i<n;i++){ x[i]=0; //Сначала все шашки на нижней горизонтали. d[i]=1; //Сначала все стрелки вверх. } while(1){ . for(i=0;i<n;i++) //Печатаем очередную последовательность. printf("%d ",x[i]); printf("\n"); for(i=n-1;i>=0 && nelzia(i);i--) //Ищем самую правую шашку, ; //которая может сделать ход. if(i==-1) break; //Если не нашли, то генерация закончена.. x[i]=x[i]+d[i]; //Если нашли, делаем ход. for(j=i+1;j<n;j++) //У шашек правее нашей d[j]=-d[j]; //Меняем направление стрелок. } getch(); return 0;}Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все его подмножества, состоящие из k элементов.
Будем считать, что элементы нашего подмножества располагаются в порядке возрастания. Начинаем с подмножества {1,2,3,…k}. По предыдущему подмножеству {x1,x2,…,xk} будем строить следующее таким образом: просматривая наше подмножество справа налево, находим самый первый элемент, не достигший максимального значения. Очевидно, что максимальное значение для xk равно n, для xk-1 – n-1 и т. д. Найденный элемент xi увеличиваем на 1, а все элементы справа от него делаем самыми маленькими из возможных: xi+1 = xi +1, xi+2 = xi+1 +1 и.т.д.
Получим следующую программу:
#include<stdio.h>
#include<conio.h>
#define n 6
#define k 3
int x[k];
main(){
int i,j;
for(i=0;i<k;i++) //Формируем начальную последовательность
x[i]=i+1;
while(1){
for(i=0;i<k;i++) //Печатаем очередную последовательность
printf("%d ",x[i]);
printf("\n");
for(i=k-1;i>=0 && x[i]==n+i-k+1;i--) //Ищем первый справа элемент, не достигший
; //максимального значения
if(i==-1) break; //Если не нашли, то заканчиваем работу.
x[i]++; //Если нашли, то увеличиваем его на 1
for(j=i+1;j<k;j++) //и заполняем правую часть
x[j]=x[j-1]+1; //минимально возможными значениями.
}
getch();
return 0;
}