265
技術社區[雲棲]
1到n的全排列
#include <iostream>
using namespace std;
void PrintElements(int *elem, int size)
{
for (int i = 1; i < size; i++)
cout << elem[i];
cout << endl;
}
void Swap(int &x, int &y)
{
int tmp = x;
x = y;
y = tmp;
}
void Reverse(int *elem, int pos, int size)
{
for (int i = pos, j = size-1; j >= i; i++, j--)
Swap(elem[i], elem[j]);
}
bool isNextPermutation(int *elem, int size)
{
int leftIndex = -1;
//從右往左尋找第一個相鄰元素中左邊元素小於右邊的元素的位置
for (int i = size-1; i >= 2; i--)
{
if (elem[i-1] < elem[i])
{
leftIndex = i-1;
break;
}
}
//如果已經完成所有排列
if (leftIndex == -1)
return false;
int rigthIndex = -1;
//從右往左尋找右邊的元素中大於前麵已經找到的元素的最小元素的位置
for (int i = size-1; i >= 2; i--)
{
if (elem[i] > elem[leftIndex])
{
rigthIndex = i;
break;
}
}
Swap(elem[leftIndex], elem[rigthIndex]);
Reverse(elem, leftIndex+1, size);
return true;
}
int main()
{
int number;//1到number進行全排列
cin >> number;
number ++;
int *elem = new int[number];
for (int i = 1; i < number; i++)
elem[i] = i;
while (true)
{
PrintElements(elem, number);
if (!isNextPermutation(elem, number))
break;
}
delete []elem;
cin.get();
return 0;
}
最後更新：2017-04-02 15:15:31