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