Note de curs, probleme algoritmică, 14 octombrie 2013

În acest curs am discutat despre generarea permutărilor prin backtracking.

Cerința 1

Să se genereze, în ordine lexicografică, toate permutările numerelor de la 1 la N.

#include <stdio.h>

int N;

bool folosit[20];
int permutare[20];

void permutari(int pos) {
	int i;
	if (pos == N) { // folosit[i] == true, oricare ar fi 1 <= i <= N
		for (i = 0; i < N; ++i) {
			printf("%d ", permutare[i]);
		}
		printf("\n");
	} else {
		for(i = 1; i <= N; ++i) {
			if (!folosit[i]) {
				folosit[i] = true;
				permutare[pos] = i;
				permutari(pos + 1);
				folosit[i] = false;
			}
		}
	}
}

int main(void) {
	// citirea datelor
	scanf("%d", &N);

	permutari(0);

	return 0;
}

Cerința 2

Să se genereze cea de-a K-a permutare, în ordine lexicografică, a numerelor de la 1 la N.

#include <stdio.h>

int N, K;

bool folosit[20];
int permutare[20];

int Factorial[20];

void permutari(int pos, int index) {
	int i;
	if (pos == N) { // folosit[i] == true, oricare ar fi 1 <= i <= N
		for (i = 0; i < N; ++i) {
			printf("%d ", permutare[i]);
		}
		printf("\n");
	} else {
		for(i = 1; i <= N; ++i) {
			if (!folosit[i]) {
				if (index < Factorial[N - (pos + 1)]) {
					folosit[i] = true;
					permutare[pos] = i;
					permutari(pos + 1, index);
					folosit[i] = false;
					return;
				} else {
					index -= Factorial[N - (pos + 1)];
				}
			}
		}
	}
}

int main(void) {
	// citirea datelor
	scanf("%d %d", &N, &K);

	int i;
	Factorial[0] = 1;
	for (i = 1; i <= N; ++i) {
		Factorial[i] = Factorial[i - 1] * i;
	}
	permutari(0, K - 1);

	return 0;
}