亲宝软件园·资讯

展开

递归之全排列算法

中微子不悲伤 人气:0

问题

假设有 {1, 2, 3, ... n} 这样一个序列,找出这个序列的所有全排列。

求解思路

第一位有 n 种可能性,确定了第一位后就是求解剩下 n - 1 个数据的排列问题,这样就可以往下一直分解问题,直到序列结尾处,也就是终止条件。

第1位排列情况(无递归)

1 2 3
2 1 3
3 2 1

暂不考虑序列元素重复问题,测试序列{1,2,3}
#include <iostream>
using namespace std;
void Perm(int list[],int from,int n)
{
    for (int i = from;i < n;i++)
    {
        swap(list[from], list[i]);
        //交换一次输出一次全排列
        for (int i = 0;i < n;i++)
            cout << list[i] << " ";
        cout << endl;
        //保证交换之前的序列还是 {1, 2, 3}
        swap(list[from], list[i]);
   
    }
}
int main()
{
    int list[] = { 1,2,3 };
    Perm(list, 0, 3);
    return 0;
}

 

所有的排列情况(递归第2位、第3位)

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
#include <iostream>
using namespace std;
void Perm(int list[],int from,int n)
{
    //循环终止条件
    if (from == n)
    {
        //交换一次输出一次全排列
        for (int i = 0;i < n;i++)
            cout << list[i] << " ";
        cout << endl;
        return;
    }
    for (int i = from;i < n;i++)
    {
        swap(list[from], list[i]);
        //加入递归
        Perm(list, from + 1, n);
        //保证交换之前的序列还是 {1, 2, 3}
        swap(list[from], list[i]);
    }
}
int main()
{
    int list[] = { 1,2,3 };
    Perm(list, 0, 3);
    return 0;
}

 

 

 

加载全部内容

相关教程
猜你喜欢
用户评论