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

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]? Верно ли, что диапазоны никогда не будут перекрываться?

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

Answer 2

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

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: исправлен для генерации комбинаций, но работает только для двух диапазонов, решение Фреда выше более масштабируемое ..

Answer 3

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

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

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

и код должен приступить к работе.