递归之全排列算法

时间:2020-03-11 中微子不悲伤人气: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位）

#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;
}

加载全部内容