Permutations &/ Combinations using c++

Question

I need a different version of permutations for my code. I could able to achieve what I want but it is not generic enough. my algorithm keeps going bigger along with my requirements. But that should not be.

This is not a home work for any one, I need it for one my critical projects, wondering if any pre-defined algorithms available from boost or any other.

Below is the standard version of next_permutation using c++.

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation

int main () 
{
  int myints[] = {1,2,3};
  do 
  {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );


  return 0;
}

That gives below output :

But my requirement is :- Let's say I have 1 to 9 numbers : 1,2,3,4,5,6,7,8,9

And I need a variable length of permutations and in only ASCENDING order and with out DUPLICATES.

Let's say i need 3 digit length of permutations then i need output as below.

123
124
125
.
.
.
128
129
134   // After 129 next one should be exactly 134
135      // ascending order mandatory
136
.
.
.
148
149
156   // exactly 156 after 149, ascending order mandatory
.
.
.
489   // exactly 567 after 489, because after 3rd digit 9, 2nd digit
567   // will be increased to 49? , so there is no possibility for
.     // 3rd digit, so first digit gets incremented to 5 then 6 then
.     // 7, in ascending order.
.     
.
.
789   // and this should be the last set I need.

My list may contain upto couple of hundred's of numbers and variable length can be 1 to up to Size of the list.

My own algorithm is working for specific variable length, and a specific size, when they both changes, i need to write huge code. so, looking for a generic one.

I am not even sure if this is called as Permutations or there is a different name available for this kind of math/logic.

Thanks in advance. musk's

You need to be more clear about what you mean by 'permutations' and 'duplicates'. As to the order, there's nothing preventing you from simply sorting the output of the permutation algo. — pvg, Dec 12 '15 at 03:34
Please check the sample list i have provided, BTW, how can i get length of 3/4/5 elements from the list containing 9 elements? Ascending order means : after 489 only 567 should be possible, with normal algorithm 490, 491,492 .... is also possible. — musk's, Dec 12 '15 at 03:48
Possible duplicate of [Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) — Saeid, Dec 12 '15 at 13:35

score 3 · Answer 1 · 2019-07-06T13:12:07.810

Formally, you want to generate all m-combinations of the set [0;n-1].

#include <iostream>
#include <vector>

bool first_combination (std::vector<int> &v, int m, int n)
{
    if ((m < 0) || (m > n)) {
        return false;
    }

    v.clear ();
    v.resize (m);
    for (int i = 0; i < m; i++) {
        v[i] = i;
    }

    return true;
}

bool next_combination (std::vector<int> &v, int m, int n)
{
    for (int i = m - 1; i >= 0; i--) {
        if (v[i] + m - i < n) {
            v[i]++;
            for (int j = i + 1; j < m; j++) {
                v[j] = v[j - 1] + 1;
            }
            return true;
        }
    }

    return false;
}

void print_combination (const std::vector<int> &v)
{
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v[i] << ' ';
    }
    std::cout << '\n';
}

int main ()
{
    const int m = 3;
    const int n = 5;

    std::vector<int> v;

    if (first_combination (v, m, n)) {
        do {
            print_combination (v);
        } while (next_combination (v, m, n));
    }
}

You can use this code and the linked article as inspiration.

Saeid · Accepted Answer · 2015-12-12T03:54:24.510

This task can be done with a simple iterative algorithm. Just increment the first element that can be incremented and rescale the elements before it until there is no element to be incremented.

int a[] = {0,1,2,3,4,5,6,7,8,9}; // elements: must be ascending in this case
int n = sizeof(a)/sizeof(int);
int digits = 7; // number of elements you want to choose
vector<int> indexes; // creating the first combination
for ( int i=digits-1;i>=0;--i ){
    indexes.push_back(i);
}

while (1){
    /// printing the current combination
    for ( int i=indexes.size()-1;i>=0;--i ){
        cout << a[indexes[i]] ;
    } cout << endl;
    ///
    int i = 0;
    while ( i < indexes.size() && indexes[i] == n-1-i ) // finding the first element
        ++i;                                            // that can be incremented
    if ( i==indexes.size() ) // if no element can be incremented, we are done
        break;
    indexes[i]++; // increment the first element
    for ( int j=0;j<i;++j ){ // rescale elements before it to first combination
        indexes[j] = indexes[i]+(i-j);
    }
}

Output:

Permutations &/ Combinations using c++

2 Answers2

Linked