PP->Алгоритмы->Перестановки

Перестановки.

Представим, что существуют пароли, состоящие из n цифр, причем каждая цифра должна принадлежать интервалу [1..n], так же цифры не могут повторяться, например пароль из трех символ может быть одним из следующих:
123
132
213
231
312
321
Так вот если существуют такие пароли, то можно написать пргограмму которая будет их перебирать. Для числа 4, это будут перестановки (возможные пароли):
1234
1243
1432
...
...
...
4321
Число таких перестановок определяется как n! Для числа 3, количество перестановок будет равно 3! = 3 * 2 * 1 = 6. Для четырех: 4! = 4 * 3 * 2 * 1 = 24.
Число 9! - уже не малое, поэтому в нашей программе сделаем ограничения для числа n, пусть оно будет находиться в интервале [1 <= n <= 9].
Для генерации перестановок используется алгоритм Дейкстры для получения всех перестановок по алфавиту.
Разберем этот алгоритм:

Пусть у нас есть первая перестановка (например 1234). Для нахождения следующей выполняем три шага. 1. Двигаясь с предпоследнего элемента перестановки, ищем элемент a[i], удовлетворяющий неравенству a[i] < a[i + 1]. Для перестановки 1234, это число 3, т. к. (3 < 4).
2. Меняем местами элемент a[i] с наименьшим элементом, который:
а) находится праве a[i].
б) является больше чем a[i].
В нашем случае меняем 3 и 4.
3. Все элементы стоящие за a[i] сортируем. В нашем случем нужно отсортировать число 4, но это единственный элемент, следовательно так его и оставляем.

В результате выполнения этих трех шагов получаем следующую по алфавиту перестановку 1243.
Выполнять эти шаги нужно циклически до тех пор, пока в перестановке не будет находится искомый в первом шаге элемент a[i], т. е. пока перестановка не станет отсортированной по убыванию: 4321.
Ниже преведенна программа на языке Си, в которой используется данный алгоритм.
В файле input.txt, находящемся в одном каталоге с программой должно быть записанно число 1 <= n <= 9, после выполнения программы, в том же каталоге появится файл output.txt, в котором на каждую строчку и будут вывденны перестановки.

				
				#include<stdio.h>
				
				#define bool int
				#define true 0
				#define false 1
				
				int main() {
					FILE *in, *out;
					int per[10], obr[10];
					int i, j, k, tmp, min, raz, n;
					bool flag;
					in   = fopen("input.txt", "r");
					out	= fopen("output.txt", "w");
					fscanf(in, "%d", &n);
					for (i = 0; i < n; i++) {
						per[i] = i+1;
					}
					while (1) {
						for (k = 0; k < n; k++) {
							fprintf(out, "%d", per[k]);
						}
						flag = false;
						for (i = n - 2; i >= 0; i--) {
							if (per[i] < per[i + 1]) {
								flag = true;
								break;
							}
						}
						if (flag == false) {
							break;
						}
						fprintf(out, "\n");
						raz = per[i+1];
						for (j = i+1; j < n; j++) {
							if (((per[j] - per[i]) < raz) && (per[i] < per[j])) {
								min = j;
							}
						}
						tmp	      = per[i];
						per[i] 	   = per[min];
						per[min] = tmp;
						for (j = i + 1; j < n; j++) {
							obr[j] = per[j];
						}
						j = i + 1;
						for (k = n-1; k >= i+1; k--) {
							per[j] = obr[k];
							j++;
						}
					}
					fclose(in);
					fclose(out);
					return 0;
				}