Getting all the combinations of a number in C++

Question

I need to get all the possible combinations of a given set. For example, given: [1, 4, 7], the resulting combinations should be:

• 111, 114, 117, 141, 144, 147, 171, 174, 177, 411, 414, 417, 441, 444, 447, 471, 474, 477, 711, 714, 717, 741, 744, 747, 771, 774, 777.

I tried using next_permutation method, but it isn't what I want (this does not return values like 111, 144, 717, etc).

So is there any way I can do this in C++? Please note that I'm a complete beginner.

Thanks in advance.

Answer 1

Have a hard look at the numbers: All numbers you listed can also be expressed as the list {11,14,17,41,44,47,71,74,77} prefixed once with 1, once with 4 and once with 7. This points to a generic rule:

The strings with 3 numbers of the set {1,4,7} are built by taking the strings with 2 numbers of the same set and prepending each element of the set.

Generalize the 3 and 2 in this rule, implement the resulting idea with recursion, and you have an algorithm for your problem.

As a C++ implementation note, make sure that you use strings instead of integers to represent your numbers. This problem is not arithmetic, and tightly coupled to the base-10 representation. Strings will make your life much easier.

Answer 2

Create an array with the values e.g. {1, 4, 7}.

Use length(array) for loops, each with length(array) iterations.

In the most inner loop output 100 * array[i] + 10 * array[j] + array[k]

If the maximum length is not known, then you use recursion instead e.g. pseudo-code:

void Solve(int[] array, int length, int position, int sum)
{
    position++;
    sum *= 10;

    for (int cnt = 0; cnt < length; cnt++)
    {
        int tempsum = sum + array[cnt];

        if (position == length)
            output(tempsum);
        else
            Solve(array, length, position, tempsum);
    }
}

Answer 3

Create a vector of integers (called vector) equal in size to the number of elements in your set. Initialize each entry to 0. Then follow this algorithm:

1) Walk vector, outputting the corresponding elements. (So if the vector is 0,1,1 and the set is [9,8,7], output 988 -- the zeroth element, the first element, the first element.)

2) Set an integer called element to 0.

3) Increment vector[element]. Check if vector[element] equals the number of elements in the set. If not go to step 1.

4) Set vector[element] to zero. Increment element. If element is less than the number of elements in the set, go to step 3.

5) Stop. You are done.

Answer 4

Have a look at my answer here : PHP take all combinations

Hint : It's not C++ code, but you'll get the idea. (I would suggest using recursion)

Answer 5

Well I took the liberty to try to implement the task. I wanted to rust off a bit my algorithm knowledge. It turned out to be like that:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<int> allowedNumbers;

bool my_next_perm(vector<int>::iterator& begin, vector<int>::iterator& end) {
    for (vector<int>::iterator itr = end - 1; ; --itr)
    {
        if (*itr != allowedNumbers.back())
        {
            *itr = *upper_bound(allowedNumbers.begin(), allowedNumbers.end(), *itr);
            while ((++itr) != end) {
                *itr = allowedNumbers[0];
            }
            return true;
        }
        if (itr == begin)
        {
            return false;
        }
    }
}
void printAllPermutationsWithRepetitions(vector<int>& v)
{
    int n = v.size();
    set<int> allNumbers;
    for (int i = 0; i < n; i++)
    {
        allNumbers.insert(v[i]);
    }
    for (set<int>::iterator itr = allNumbers.begin(); itr != allNumbers.end(); ++itr) {
        allowedNumbers.push_back(*itr);
    }
    for (int i = 0; i < n; i++) {
        v[i] = allowedNumbers[0];
    }

    do {
        for (int i = 0; i < n; i++) {
            if (i != 0) cout << " ";
            cout << v[i];
        }
        cout << endl;
    } while(my_next_perm(v.begin(), v.end()));
}

int main (int argc, char *argv[]) {
    vector<int> v;
    v.push_back(7);
    v.push_back(1);
    v.push_back(3);
    printAllPermutationsWithRepetitions(v);
    return 0;
}

The implementation is just slightly suboptimal (because I use upper_bound).

Answer 6

You're effectively counting with a base of 3 from 000 to 222, looking up your array of [1, 4, 7] with those digits as indices. Generalising this to work with arbitrary sized input array:

int n = digits.size();
int n_n = std::pow(n, n);
for (int i = 0; i < n_n; ++i)
{
     int x = i;
     for (int j = 0; j < n; ++j)
     {
          cout << digits[x % n];
          x /= n;
     }
     cout << ' ';
}

Answer 7

This is the simplest way of doing this. You can take any number as input from user like 147 and it will print all permutations as: 111, 114, 117, 141, 144, 147, 171, 174, 177, 411, 414, 417, 441, 444, 447, 471, 474, 477, 711, 714, 717, 741, 744, 747, 771, 774, 777.

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

 bool Search(int A[],int num,int length)
    {
        for(int i = 0;i<length;i++)
            if(A[i] == num)
                return 1;
        return 0;
    }


    int main()
    {
        int n;
        cout << "Please Enter a Number\n";
        cin>>n;
        int num = n, k = 1;
        int count = 0;
        while(num>0)
        {
            num/=10;
            count++;
        }
        cout<<"The All Permutations of " <<n<<" are: "<<endl;
        num = n;
        int *A = new int[count];

        for(int i = 0;i<count;i++)
        {
            A[i] =  num%10;
            num/=10;
        }


        int fact = pow(count,count);
        int *Ar = new int[fact];
        int *B = new int[count];
        int value,number = 0;

        for(int i = 0;i<fact;)
        {

            for(int j = 0;j<count;++j)
            {
                value = (rand()%count);

                B[j] = value;
            }

            for(int k= 0;k<count;k++)
                number = number + A[B[k]]*pow(10,k);

            if(Search(Ar,number,fact) == 0)
            {
                cout<<k++<<". "<<number<<endl;
                Ar[i] = number;
                ++i;
            }
            number = 0;

        }

        return 0;
    }