Генериране на пермутации без рекурсия с next_permutation
На ANSI C++, с използване на стандартната библиотека с алгоритми и структури от данни (STL)
#include
#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, а елементите й с pi
Първата пермутация е 1 2 3
Повтаряме следното
Обхождаме масива P отдясно-наляво
Търсим индекс i: p i < p i+1
Търсим индекс j: p i > p j , p j = min(p i+1, … p n)
Разменяме pi с pj
Обръщаме реда на елементите 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 елемента
Пример
1
|
12
21
|
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;
}
|
Сподели с приятели: |