使用递归对 int 数组进行排列

Question

练习如下：

Generate every possible sequence whose elements are from the set {0, 1, 2} where 0 occurs m times, 1 occurs p times, and 2 occurs q times. The input file contains three natural numbers separated by spaces, with a maximum value of 100. The solution must be written to the output file line by line in lexicographic order. Each line should contain the elements of the series separated by spaces.

If input is:
1 0 2

Output should be:
0 2 2
2 0 2
2 2 0

还说，我必须使用递归，输入和输出应该是.txt文件。

所以，我发现了一个流行的排列递归，它发生在多个站点上（比如 this），但是由于一些奇怪的原因，它对我来说不能正常工作..

我尝试做这个练习的方法（可能有更聪明的方法）是从输入生成一个向量，并使用它的置换函数。但是我的输出是这样的：

大家可以看到，每个结果都出现了两次，明显不好..

代码如下：

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

void input(int& m, int& p, int& q)
{
    ifstream fin("input.txt");

    fin >> m >> p >> q;
    
    fin.close();
}

void fillVec(vector <int>& elements, int m, int p, int q)
{
    fill_n(elements.begin() + m, p, 1); // filling the vectors with correct amount of numbers. The 0's all already there, so I only put the 1's, and the 2's in.
    fill_n(elements.begin() + m + p, q, 2);
}

void print(const vector<int>& nums, ofstream& fout)
{
    for (int a : nums) { fout << a << ' '; }
    fout << endl;
}

void permute(vector<int>& nums, int n, ofstream& fout) 
{
    if (n == nums.size()) 
    {
        print(nums, fout); 
    } 
    else 
    {
        for (int i = n; i < nums.size(); i++) 
        {
            swap(nums[n], nums[i]);
            permute(nums, n + 1, fout); 
            swap(nums[n], nums[i]);  
        }
    }
}

int main()
{
    int m, p, q;

    input(m, p, q);

    vector <int> elements(m + p + q);
    fillVec(elements, m, p, q);

    ofstream fout("output.txt");

    permute(elements, 0, fout);
    
    fout.close();

    return 0;
}

我尝试调试，也多次查看以检查我是否正确复制了算法，但无法找出问题所在。这可能很简单，我不确定..

Answer 1

如您所见和所说，您只需生成 0 2 2 数组的所有可能排列。长度为 3 的数组有 6 个排列，你正确地得到了它们，但是因为有两个相等的数字，所以其中一些排列是相等的。

但是，显然您需要的是仅生成 不同的 排列。基本上，这意味着您需要一种新算法。

一个简单的解决方案可能是找到一种方法来删除重复排列。可能有很多方法，首先是简单地存储所有排列并检查您是否已经生成了给定的排列，或者存储每个数字的原始数组索引并要求相同数字的索引按递增顺序排列，等等。或者你可以用不同的方式组织你的递归（这就是我会做的）。显然每种方法的复杂度都会不同。

Answer 2

使用 std::next_permutation（处理重复），非递归方式是：

void permute(std::vector<int>& nums, std::ostream& out) 
{
    assert(std::is_sorted(nums.begin(), nums.end()));
    do {
        print(nums, out); 
    } while (std::next_permutation(nums.begin(), nums.end()));
}

Demo

你仍然可以递归地转换上面的代码：

void permute(std::vector<int>& nums, std::ostream& out) 
{
    print(nums, out); 
    if (std::next_permutation(nums.begin(), nums.end())) { permute(nums, out); }
}

Demo

Answer 3

您的代码很完美，可以按预期工作。唯一的问题是您的应用程序有时会交换相同的数字，例如：

// nums = {0, 2, 2}
swap(nums[n], nums[i]); // n == 1, i == 2
// nums = {0, 2, 2}

在这里你可以注意到应用程序将交换 2 和 2，这不会有任何区别。

因此您可以尝试这样的操作：

#include <iostream>
#include <vector>
#include <fstream>

// This std::vector will store all the elements that have been stored in output.txt
std::vector<std::string> output;

void input(int& m, int& p, int& q)
{
    std::ifstream fin("input.txt");

    fin >> m >> p >> q;

    fin.close();
}

void fillVec(std::vector <int>& elements, int m, int p, int q)
{
    fill_n(elements.begin() + m, p, 1); // filling the std::vectors with correct amount of numbers. The 0's all already there, so I only put the 1's, and the 2's in.
    fill_n(elements.begin() + m + p, q, 2);
}

void print(const std::vector<int>& nums, std::ofstream& fout)
{
    for (int a : nums) { fout << a << ' '; }
    fout << std::endl;
}

void permute(std::vector<int>& nums, int n, std::ofstream& fout)
{
    if (n == nums.size())
    {
        std::string num;

        // Convert nums (int array) to num (std::string)
        for (int i = 0; i < nums.size(); i++) 
        {
            num.push_back(nums[i]);
        }

        // If same element found, return
        for (int i = 0; i < output.size(); i++)
        {
            if (num == output[i]) return;
        }
        print(nums, fout);

        // Insert element to output (std::vector)
        output.push_back(num);
    }
    else
    {
        for (int i = n; i < nums.size(); i++)
        {
            std::swap(nums[n], nums[i]);
            permute(nums, n + 1, fout);
            std::swap(nums[n], nums[i]);
        }
    }
}

int main()
{
    int m, p, q;

    input(m, p, q);

    std::vector <int> elements(m + p + q);
    fillVec(elements, m, p, q);

    std::ofstream fout("output.txt");

    permute(elements, 0, fout);

    fout.close();

    return 0;
}

此代码与您的代码相同，只是我添加了一些检查以确保没有重复元素。现在：

input.txt

1 0 2

output.txt（应用程序执行后）

0 2 2 
2 0 2 
2 2 0

...这是可取的。

此外，考虑删除以下语句：

using namespace std;

...因为它被认为是不好的做法。

Answer 4

这是我想出的。每个递归步骤都会尝试将“0”、“1”或“2”附加到正在构建的字符串中，直到没有可用的数字可添加为止。

#include <iostream>
#include <string>

using namespace std;

void GeneratePermutations(int zeros, int ones, int twos, const string& leading)
{
    if ((zeros <= 0) && (ones <= 0) && (twos <= 0))
    {
        // use "substr" to skip the leading space
        if (leading.size() > 0)
        {
            std::cout << leading.substr(1) << endl;
        }

        return;
    }
  
    if (zeros > 0)
    {
        GeneratePermutations(zeros - 1, ones, twos, leading + " 0");
    }

    if (ones > 0)
    {
        GeneratePermutations(zeros, ones-1, twos, leading + " 1");
    }

    if (twos > 0)
    {
        GeneratePermutations(zeros, ones, twos-1, leading + " 2");
    }
}


int main()
{
    int zeros, ones, twos;

    cin >> zeros;
    cin >> ones;
    cin >> twos;

    GeneratePermutations(zeros, ones, twos, "");

    return 0;
}

几个样本运行：

输入：1 0 2

输出：

0 2 2
2 0 2
2 2 0

另一个输入：3 1 1

输出：

使用递归对 int 数组进行排列

Permutations of an int array, using recursion

c++

algorithm

recursion

vector

input.txt

output.txt（应用程序执行后）