几种求排列数的方法例如:给出n=3求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3

来源：学生作业帮编辑：作业帮分类：综合作业时间：2024/07/13 22:28:38

几种求排列数的方法
例如:给出n=3
求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 2 1
一共有几种算法可以求出这个结果呀?

前面的热心网友回答的那种穷举法可以,但比较耗时且不易扩展.
全排列问题其实就是一个深度搜索的问题,一般采取回溯法来解决.
当然就具体问题还要考虑剪枝等细节问题,不过你这里只是全排列就不用考虑那么多了.
比较有名的题目是八皇后问题.

下面给一个全排列问题的递归解法,改变N的值可以对不同数进行全排列.
如果要求输入n来全排列的话把数组a改成动态分配,并作为参数送入各个函数就行了.

#include <iostream>
using namespace std;
#define N 3
int a[N];
void printSeq()
{
for(int i=0; i<N; i++) cout << a[i] << " ";
cout << endl;
}
bool isok(int i, int k)
{
for(int j=0; j<i; j++)
{
  if(a[j] == k) return false;
}
return true;
}
void calcSeq(int i)
{
if(i==N) printSeq();
else
{
  for(int k=1; k<=N; k++)
  {
   if(isok(i, k))
   {
    a[i] = k;
    calcSeq(i+1);
   }
  }
}
}
int main()
{
calcSeq(0);
return 0;
}

另外也有非递归解法,模拟一个栈来做

几种求排列数的方法例如:给出n=3求得所有的排列数为 1 2 3 ,1 3 2,2 1 3,2 3 1,3 1 2 ,3 计算排列的逆序数:n(n-1)(n-2)(n-3)……21 给出依次排列的一列数:1,-2,3,-4,5,-6,…试找出这一列数排列的一个规律? 给出一个一次排列的数1,-3,5,-7,9…,请按规律写出第n个数为 1,2,3,4四个数选两个数排列,共几种排列? 给出依次排列的一列数:1,-3,5,-7,9的后三个数给出依次排列的一列数：-1,2,-4,8,-16,32,...第n个数是? 求排列的逆序数1 3…（2n—1）2 4…（2n）按自然数从大到小为标准次序,求这个排列的逆序数. 给出依次排列的一列数：-1,2,-4,8,-16,32......按照此规律,第N个数为? 给出依次排列的一列数；-1,2,-4,8,-16,32 按照规律,第n个数为【】求2n元排列2n 1 2n-1 2 2n-2 3 2n-3 .n+1 n的逆序数. 关于排列逆序数的计算2n（2n-2）…2（2n-1）（2n-3）…1 请问如何计算该排列的逆序数?