CODEWITHSUNDEEP
c++vectorpermutation
Radek Simko
Radek Simko

Reputation: 16146

Permutations of multiple ranges of numbers

I need to generate permutations from multiple ranges of numbers in array.

using namespace std;

int generatePermutations(vector<int> &myVector, vector<vector<int> > &swappable) {
    int i = 0, s = 0;
    for (s = 0; s < swappable.size(); s++) {
        do {
            for (i = 0; i < myVector.size(); i++) {
                printf("%i ", myVector[i]);
            }
            printf("\n");
            swappable.pop_back();
            generatePermutations(myVector, swappable);
        } while (next_permutation(myVector.begin()+swappable[s][0],
                myVector.begin()+swappable[s][1]));
    }
}

int main() {
    vector<int> myArray;
    myArray.resize(6);
    myArray[0] = 0;
    myArray[1] = 1;
    myArray[2] = 2;
    myArray[3] = 3;
    myArray[4] = 4;
    myArray[5] = 5;

    // Swappable positions (0 - first, 1 - last)
    vector<vector<int> > swappable;
    swappable.resize(2);
    swappable[0].resize(2);
    swappable[0][0] = 1; swappable[0][1] = 3;
    swappable[1].resize(2);
    swappable[1][0] = 4; swappable[1][1] = 6;
    generatePermutations(myArray, swappable);

    return 0;
}

The example above should generate something like this:

0 1 2 3 4 5
0 2 1 3 4 5
0 1 2 3 5 4
0 2 1 3 5 4

But it generates this:

0 1 2 3 4 5
0 1 2 3 4 5

Upvotes: 2

Views: 704

Answers (3)

Nim
Nim

Reputation: 33645

Here is a slightly modified version of your generation algorithm (which is broken).

int generatePermutations(vector<int> &myVector, vector<vector<int> >& swappable) {
  do
  {
    do
    {
      print(myVector);
      // generate permutations of the second segment
    } while(next_permutation(myVector.begin() + swappable[1][0], myVector.begin() + swappable[1][1]));

    // re-sort the second segment
    sort(myVector.begin() + swappable[1][0], myVector.begin() + swappable[1][1]);

    // calculate permutation of first segment
  } while(next_permutation(myVector.begin() + swappable[0][0], myVector.begin() + swappable[0][1]));
}

EDIT: fixed now to generate the combinations, but only works for two ranges, Fred's solution above is more scalable..

Upvotes: 0

Bart van Ingen Schenau
Bart van Ingen Schenau

Reputation: 15768

You have created a seemingly correct iterative solution for the problem, but in each iteration, you remove an element from the swappable vector and make a recursive call.
As both myVector and swappable are passed by non-const reference, these recursive calls destroy the contents of the swappable vector before you are actually generating permutations.

Just remove the lines

swappable.pop_back();
generatePermutations(myVector, swappable);

and the code should start to work.

Upvotes: 0

Fred Nurk
Fred Nurk

Reputation: 14212

I take it swappable is a set of ranges which may be swapped? So [[1, 3], [4, 6]] means anything in [1, 3) (indexes 1 and 2) can be swapped around in that range, and similarly for [4, 6)? Is it also true that the ranges will never overlap?

How does this look:

typedef vector<vector<int> >::const_iterator SwappableIter;
void generatePermutations(vector<int> &data,
                          SwappableIter begin, SwappableIter end)
{
  if (begin == end) {
    print(data);
  }
  else {
    vector<int>::iterator start = data.begin() + (*begin)[0],
      stop = data.begin() + (*begin)[1];
    sort(start, stop);
    do {
      generatePermutations(data, begin + 1, end);
    } while (next_permutation(start, stop));
  }
}

Upvotes: 2

Related Questions