Генериране на пермутации без рекурсия с next permutation

Изтегляне 21.96 Kb.

Дата	25.07.2016
Размер	21.96 Kb.
	#6564

Генериране на пермутации без рекурсия с next_permutation

На ANSI C++, с използване на стандартната библиотека с алгоритми и структури от данни (STL)

#include

int main ( )

{
char v[ ] = "abcd";

do {

cout << v << endl;

} while (next_permutation( v, v + 4));
return 0;

}

Лексикографски алгоритъм за генериране на пермутации

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1
Описание на алгоритъма

Ще отбелязваме пермутaцията с P, а елементите й с p_i

Първата пермутация е 1 2 3

Повтаряме следното

Обхождаме масива P отдясно-наляво

Търсим индекс i: p _i < p _i+1

Търсим индекс j: p _i> p _j , p _j= min(p _i+1, … p _n)

Разменяме p_iс p_j

Обръщаме реда на елементите p _i+1,…., p _n

1

2

3

4

i

j

1

2

4

3

i

j

1

3

2

4

i

j

1

3

4

2

i

j

1

4

2

3

…

Генериране на пермутации с рекурсивни алгоритми

Генериране на пермутации с вмъкване на n-ти елемент на всяко възможно място в пермутация от n-1 елемента
Пример

312

132

123
321

231

213

На С с рекурсия

#include
#define MAXN 100
const unsigned n = 5;
unsigned a[MAXN];
void print(void)

{ unsigned i;

for (i = 0; i < n; i++) printf("%u ", a[i] + 1);

printf("\n");

}
void permut(unsigned k)

{ unsigned i, swap;

if (k == 0) print();

else {

permut(k - 1);

for (i = 0; i < k - 1; i++) {

swap = a[i]; a[i] = a[k-1]; a[k-1] = swap;

permut(k - 1);

swap = a[i]; a[i] = a[k-1]; a[k-1] = swap;

}

int main(void) {

unsigned i;

for (i = 0; i < n; i++) a[i] = i;

permut(n);

return 0;

}

Каталог: res -> I 6 gm 01 0910
res -> На Блайт, Дължа благодарност на Емили Бестлър, Джейсън Ка
res -> Космически граници
res -> Соу „СВ. Св. Кирил и методий
res -> Списък на издадените сертификати за продукти
res -> На предложение Дата Съдържание на предложението
res -> Побитови операции
I 6 gm 01 0910 -> За числата 1,2, 3, 4, 5, 6 a кое число попада на 124та позиция?

Изтегляне 21.96 Kb.

Сподели с приятели: