输入一组不重复数字，全排列

亦凉 2023-02-26 05:23 14阅读 0赞

全排列是我们读书时课堂上已经学过东西，给出1，2，3三个数，有多少个组合方式呢？  
123，132，213，231，312，321  
很快我们就能给出这组数的全排列，全排列个数=N\*(N-1)\*(N-2)\*…\*1=N!

看起来很easy,我以为代码实现起来分分钟的事情，然后并没有  
这是我一口气写完的代码，输出却什么都没有

vector<vector<int> > Permutation(vector<int> num_list)
    {
        
        vector<vector<int> > d_list;
        for (int i = 0; i < num_list.size(); i++)
        {
        
            vector<int> i_list = num_list;
            i_list.erase(i_list.begin() + i);
            vector<vector<int> > temp_list = Permutation(i_list);
            for (int j = 0; j < temp_list.size(); j++)
            {
        
                vector<int> j_lis = temp_list.at(j);
                j_lis.insert(j_lis.begin(), num_list.at(i));
                d_list.push_back(j_lis);
            }
        }
        return d_list;
    }

最后发现，当输入一个空列表时，返回一个空列表，最后在for (int j = 0; j < temp\_list.size(); j++)时，没有得到插入当前前值。修改后我们看下

vector<vector<int> > Permutation(vector<int> num_list)
    {
        
        vector<vector<int> > d_list;
        if (num_list.size() == 0 )
        {
        
            d_list.push_back(vector<int>());
            return d_list;
        }
        for (int i = 0; i < num_list.size(); i++)
        {
        
            vector<int> i_list = num_list;
            i_list.erase(i_list.begin() + i);
            vector<vector<int> > temp_list = Permutation(i_list);
            for (int j = 0; j < temp_list.size(); j++)
            {
        
                vector<int> j_lis = temp_list.at(j);
                j_lis.insert(j_lis.begin(), num_list.at(i));
                d_list.push_back(j_lis);
            }
        }
        return d_list;
    }
    int main(int argc, char *argv[])
    {
        
        vector<int> list_num;
        list_num.push_back(1);
        list_num.push_back(2);
        list_num.push_back(3);
        vector<vector<int> > PermutationList =   Permutation(list_num);
        for (int i = 0; i < PermutationList.size(); i++)
        {
        
            printf("\n");
            for (int j = 0; j < PermutationList.at(i).size(); j++)
            {
        
                printf("%d\t",PermutationList.at(i).at(j));
            }
        }
        printf("\n");
        return 0;
    }
    /* 输出结果：
    1	2	3	
    1	3	2	
    2	1	3	
    2	3	1	
    3	1	2	
    3	2	1
    */