Permutations of an int array, using recursion-CodePudding

Exercise is as follows:

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

It's also stated, that I have to use recursion, and the input and output should be to .txt files.

So, I found a popular recursion for permutations which occurred on multiple sites (like this), but for some weird reason, it's not working properly for me..

The way I tried doing this exercise (there might be a smarter way) is by generating a vector from the input, and the using the permutation function with it. But my output is like this:

As you can see, every result appears twice, which is obviously not good..

Code is here below:

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

I tried debugging, also looked at it multiple times to check that I copied the algorithm correctly, but can't find out what's the problem. It might be something pretty simple, I'm not sure..

CodePudding user response：

Here's what I came up with. Each recursive step will attempt to append "0", "1", or "2" to the string being built until there's no available digits to add.

It winds up printing a trailing space on each output line. If that's relevant, I'll leave that as minor bug for you to fix.

#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))
    {
        std::cout << leading << 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;
}

A couple of sample runs:

input : 1 0 2

output:

0 2 2
2 0 2
2 2 0

Another input: 3 1 1

output:

CodePudding user response：

As you see and say yourself, you simply generate all possible permutations of the 0 2 2 array. There are 6 permutations for an array of length 3, and you correctly get them, but because there are two equal numbers, some of these permutations are equal.

However, apparently what you are required is to do generate only different permutations. Basically, this means that you need a new algorithm.

A simple solution may be to find a way to remove repeating permutations. There may be many approaches to it, starting with simply storing all the permutations and checking if you have already generated a given permutation, or storing the original array index with each number and requiring that the indices of equal number go in increasing order, etc. Or you can organize your recursion in a different way (that's what I would have done). Obviously the complexity of each approach will be different.

CodePudding user response：

With std::next_permutation (which handles repetitions), a non recursive way would be:

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

You can still transform above code in recursive way:

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

Demo

CodePudding user response：

Your code is perfect and works as expected. The only problem is that your application is sometimes swapping the same digits, for example:

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

Here you can notice that the application will swap 2 and 2, which will not make any difference.

Thus you can try something like this:

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

This code is the same as yours, except I've added a few checks to ensure that there are no duplicate elements. Now:

input.txt

1 0 2

output.txt (after application execution)

0 2 2 
2 0 2 
2 2 0

...which is desirable.

Also, consider removing the following statement:

using namespace std;

...as it's considered as bad practice.