How to Create All Permutations of Variables from a Variable Number of STL Vectors

Question

I have a variable number of std::vectors<int>, let's say I have 3 vectors in this example:

std::vector<int> vect1 {1,2,3,4,5};
std::vector<int> vect2 {1,2,3,4,5};
std::vector<int> vect3 {1,2,3,4,5};

The values of the vectors are not important here. Also, the lengths of these vectors will be variable.

From these vectors, I want to create every permutation of vector values, so:

{1, 1, 1}
{1, 1, 2}
{1, 1, 3}
...
...
...
{3, 5, 5}
{4, 5, 5}
{5, 5, 5}

I will then insert each combination into a key-value pair map for further use with my application.

What is an efficient way to accomplish this? I would normally just use a for loop, and iterate across all parameters to create all combinations, but the number of vectors is variable.

Thank you.

Edit: I will include more specifics.

So, first off, I'm not really dealing with ints, but rather a custom object. ints are just for simplicity. The vectors themselves exist in a map like so std::map<std::string, std::vector<int> >.

My ultimate goal is to have an std::vector< std::map< std::string, int > >, which is essentially a collection of every possible combination of name-value pairs.

Answer 1

0 - > 0,0,0

1 - > 0,0,1

2 - > 0,1,0

3 - > 0,1,1

4 - > 1,0,0

...

7 - > 1,1,1

8 - > 1,1,2

...

The map should translate a linear integer into a combination (ie: a1,a2,a3...an combination) that allows you to select one element from each vector to get the answer.

There is no need to copy any of the values from the initial vectors. You can use a mathematical formula to arrive at the right answer for each of the vectors. That formula will depend on some of the properties of your input vectors (how many are there? are they all the same length? how long are they? etc...)

Answer 2

Many (perhaps most) problems of the form "I need to generate all permutations of X" can be solved by creative use of simple counting (and this is no exception).

Let's start with the simple example: 3 vectors of 5 elements apiece. For our answer we will view an index into these vectors as a 3-digit, base-5 number. Each digit of that number is an index into one of the vectors.

So, to generate all the combinations, we simply count from 0 to 5³ (125). We convert each number into 3 base-5 digits, and use those digits as indices into the vectors to get a permutation. When we reach 125, we've enumerated all the permutations of those vectors.

Assuming the vectors are always of equal length, changing the length and/or number of vectors is just a matter of changing the number of digits and/or number base we use.

If the vectors are of unequal lengths, we simply produce a result in which not all of the digits are in the same base. For example, given three vectors of lengths 7, 4 and 10, we'd still count from 0 to 7x4x10 = 280. We'd generate the least significant digit as N%10. We'd generate the next least significant as (N/10)%4.

Presumably that's enough to make it fairly obvious how to extend the concept to an arbitrary number of vectors, each of arbitrary size.

Answer 3

This is an explicit implementation of what Lother and Jerry Coffin are describing, using the useful div function in a for loop to iterate through vectors of varying length.

#include <cstdlib> // ldiv
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

vector<int> vect1 {100,200};
vector<int> vect2 {10,20,30};
vector<int> vect3 {1,2,3,4};

typedef map<string,vector<int> > inputtype;
inputtype input;
vector< map<string,int> > output;

int main()
{
  // init vectors
  input["vect1"] = vect1;
  input["vect2"] = vect2;
  input["vect3"] = vect3;

  long N = 1; // Total number of combinations
  for( inputtype::iterator it = input.begin() ; it != input.end() ; ++it )
    N *= it->second.size();

  // Loop once for every combination to fill the output map.
  for( long i=0 ; i<N ; ++i )
  {
    ldiv_t d = { i, 0 };
    output.emplace_back();
    for( inputtype::iterator it = input.begin() ; it != input.end() ; ++it )
    {
      d = ldiv( d.quot, input[it->first].size() );
      output.back()[it->first] = input[it->first][d.rem];
    }
  }

  // Sample output
  cout << output[0]["vect1"] << endl; // 100
  cout << output[0]["vect2"] << endl; // 10
  cout << output[0]["vect3"] << endl; // 1
  cout << output[N-1]["vect1"] << endl; // 200
  cout << output[N-1]["vect2"] << endl; // 30
  cout << output[N-1]["vect3"] << endl; // 4

  return 0;
}

Answer 4

Use a vector array instead of separate variables. then use following recursive algorithm :-

permutations(i, k, vectors[], choices[]) {
    if (i < k) {
        for (int x = 0; x < vectors[i].size(); x++) {
            choices[i] = x;
            permutations(i + 1, k, vectors, choices);
        }
    } else {
        printf("\n %d", vectors[choices[0]]);
        for (int j = 1; j < k; j++) {
            printf(",%d", vectors[choices[j]]);
        }
    }
}

Answer 5

Following may help: (https://ideone.com/1Xmc9b)

template <typename T>
bool increase(const std::vector<std::vector<T>>& v, std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] == v[index].size()) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

template <typename T>
void do_job(const std::vector<std::vector<T>>& v, std::vector<std::size_t>& it)
{
    // Print example.
    for (std::size_t i = 0, size = v.size(); i != size; ++i) {
        std::cout << v[i][it[i]] << " ";
    }
    std::cout << std::endl;
}

template <typename T>
void iterate(const std::vector<std::vector<T>>& v)
{
    std::vector<std::size_t> it(v.size(), 0);

    do {
        do_job(v, it);
    } while (increase(v, it));
}