排列组合(1)——递归函数

最近，在学习数据结构的中的栈和队列，看到了关于栈的一个比较经典的例子，就是关于我们生活中经常遇到的排列组合问题，下面我们来看看如何用编程实现。

开始前的一些说明

使用的语言：C#（窗体程序）
使用的工具：Visual Studio 2019

整体思路

如右图所示：对于四个数的排列，把它想象成占位置，先用"1"占第一个位置，然后在考虑第二个位置的归属，分别可能是"2"、"3"、"4"，决定好第二个位置之后，再考虑第三个位置的归属，这样依次下去......通过for循环实现每一列数的选择，再通过递归实现行的选择。（其实就是通过for循环从1-4中选出一个数出来，而放在哪个位置就通过递归进行选择）

核心代码

public void Fun_Permute_Recursion(int n, int m, int k)
{
    for (int i = 1; i <= n; i++)//从1-n中选数
    {
        bool tag = false;
        for (int j = 1; j <= k - 1; j++)//把新的要选进来的数和数组里的数进行比较，看有没有重复的
        {
            if (i == m_percom_temp[j])
            { 
                tag = true; break; 
            }
        }
        if (tag == false)
        {
            m_percom_temp[k] = i;
            if (k < m)//判断当前是否已经选满
            {
                Fun_Permute_Recursion(n, m, k + 1);//进行下一个位置的选择
            }
            else
            {
                m_strout += Getstr_percom_temp(m);//选好了进行输出
            }
        }
    }
}

关键部分代码的解释：

Fun_Permute_Recursion函数的几个参数：
n：总数
m：从n总选出的个数
k：现在要排第几个位置

tag：作为一个判断的条件，当有重复的数时，为false；否则，为true

m_percom_temp：用来存储排好的数。每一次排好一组就输出一组，新生成的一组再原来的基础上进行覆盖。

函数的补充

Getstr_percom_temp(m):

    public string Getstr_percom_temp(int m)
{
    string strout = "";
    string str = "";
for(int i = 1; i <= m; i++)
{
    if(i != m)
    {
        str +=  Convert.ToString(m_percom_temp[i])+",";
    }
    else
    {
        str += Convert.ToString(m_percom_temp[i]);
    }
}
    strout = "（" + count + "）\t\t" + "【" + str + "】\n";
        count++;
    return strout;
}

运行结果展示

后记

排列组合问题很好的将递归函数的特性展现了出来，其实递归函数的思想也包含于栈当中，是栈的一个具体体现。如果这篇文章当中有什么不对的地方希望大家能够帮忙指正，有什么不懂的地方欢迎交流！

排列组合(1)——递归函数

原文：https://www.cnblogs.com/cnmkybw/p/data_structure.html