Перестановки нескольких диапазонов чисел

Question

Мне нужно генерировать перестановки из нескольких диапазонов чисел в массиве.

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;
}

Пример выше должен генерировать что-то вроде этого:

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

Но он генерирует это:

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

Answer 1

Я так понимаю, это подкачка - это набор диапазонов, которые можно поменять местами? Таким образом, [[1, 3], [4, 6]] означает, что что-либо в [1, 3) (индексы 1 и 2) можно поменять местами в этом диапазоне, и аналогично для [4, 6)? Также верно, что диапазоны никогда не будут перекрываться?

Как это выглядит:

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));
  }
}

Answer 2

Вы создали, казалось бы, правильное итеративное решение проблемы, но на каждой итерации вы удаляете элемент из вектора swappable и делаете рекурсивный вызов.
Поскольку и myVector, и swappable передаются не const ссылкой, эти рекурсивные вызовы уничтожают содержимое вектора swappable до того, как вы на самом деле генерируете перестановки.

Просто удалите строки

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

и код должен начать работать.

Answer 3

Вот слегка измененная версия вашего алгоритма генерации (который не работает).

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]));
}

РЕДАКТИРОВАТЬ: исправлено теперь для генерации комбинаций, но работает только для двух диапазонов, решение Фреда выше, является более масштабируемым ..