C++: How to Generate All Combinations of a Vector of Digits of Length N, disregarding order?

Question

So I need to combine a specific number (not string) of digits from a vector of possible ones (all 0-9, not characters) in an N-digit number (not binary, then). However, I cannot have any extra permutations appear: for example 1234, 4321, 3124... are now the same and cannot be all outputed. Only one can be. This is hard because other questions cover these permutions by using std::next_permutation, but I still need the different combinations. My attempts at trying to remove permutations have failed, so how do you do this? Here is my current code with comments:

#include <iostream>
#include <vector>
using namespace std;
#define ll long long

int n = 0, m = 0, temp; //n is number of available digits
//m is the length of the desired numbers
//temp is used to cin
vector <int> given;
//vector of digits that can be used
vector <int> num;
//the vector to contain a created valid number
void generate(vector <int> vec, int m) {
    //recursive function to generate all numbers
    if (m == 0) {
        for (int x : num) {
            cout << x;
        }
        cout << '\n';
        return;
    }
    for (int i = 0; i < given.size(); i++) {
        num.push_back(given[i]); //add digit to number
        int save = given[i];
        given.erase(given.begin() + i);
        //no repeating digits, save the used one and delete
        //however, permutations can still pass, which is undesirable
        generate(vec, m - 1);
        //recursive
        num.pop_back();
        //undo move
        given.insert(given.begin() + i, save);
        //redo insert deleted digit
    }
}
int main () {
    cin >> n;
    //input number of available digits
    for (int i = 0; i < n; i++) {
        cin >> temp;
        given.push_back(temp); //input digits
    }
    cin >> m;
    //input length of valid numbers
    generate(given, m); //start recursive generation function
    return 0;
}

I tried deleting permutations before printing them and erasing more digits to stop generating permutations, but they all failed. Lots of other questions still used std::next_permutation, which was not helpful.

Please take some time to read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) Also note that type-aliases like `ll`, many global variables and short undescriptive names are other bad habits you need to train yourself to not use. Bad habits are bad, even on so-called "competition" sites, so please use good habits even for those. — Some programmer dude, Jan 22 '23 at 15:20
If you always sort the digits in ascending order, and store the generated permutations in some kind of data structure, it will be easy to find the duplicate permutations. There is probably much more efficient methods though. — Sven Nilsson, Jan 22 '23 at 15:21
"A combination is a combination of n things taken k at a time without repetition.” So you do this using next_permutation but for a binary string. eg for 3 digits {1,1,1,0,0,0,0,0,0,0} then use permutations of this to select 3 from 10 digits to use. — QuentinUK, Jan 22 '23 at 18:06

score 1 · Accepted Answer · edited Jan 25 '23 at 12:43

Unlike some people who suggested binary strings in some comments, you can begin by having a recursive function that can go two ways as an on/off switch to decide whether or not to include a given digit. I personally like using a recursive function to do this and a check for length at the end to actually print the number of the desired len, demonstrated in the code below:

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int givencount = 0, temp = 0, len = 0;
vector <int> given;
string creatednum;
void generate(int m) {
    if (m == givencount) {
        if (creatednum.length() == len) {
            cout << creatednum << '\n';
        }
        return;
    }
    for (int i = 0; i < 2; i++) {
        if (i == 1) {
            generate(m + 1);
            continue;
        }
        creatednum = creatednum + ((char) ('0' + given[m]));
        generate(m + 1);
        creatednum.erase(creatednum.begin() + creatednum.length() - 1);
    }
}
int main () {
    cin >> givencount;
    for (int i = 0; i < givencount; i++) {
        cin >> temp;
        given.push_back(temp);
    }
    cin >> len;
    generate(0);
    return 0;
}

C++: How to Generate All Combinations of a Vector of Digits of Length N, disregarding order?

1 Answers1