C++ перебирать все перестановки соседства

Question

У меня есть вектор из N объектов, и я хотел бы перебирать все соседние перестановки этого вектора. То, что я называю сосед перестановку является перестановкой, где только два элемента исходного вектора будет изменен: , если у меня есть вектор с 'a','b','c','d' затем:

'b','a','c','d' //is good 
'a','c','b','d' //is good 
'b','a','d','c' //is not good (2 permutations) 

Если я использую std::next_permutation(myVector.begin(), myVector.end() тогда я получу все возможные перестановки , а не только «соседние» ...

Вы не знаете, как это можно достичь?

Answer 1

Первоначально я думал, что фильтр перестановок, которые имеют hamming distance больше 2.

Однако, если вам действительно нужно только генерировать все векторы в результате путем замены одной пары, было бы более эффективным, если вы сделать так:

for(int i = 0; i < n; i++) 
    for(int j = i + 1; j < n; j++) 
     // swap i and j 

в зависимости от того, нужно ли собрать все результаты или нет, вы должны сделать копию или вектор перед своп или своп снова я и J после обработал текущую перестановку.

Соберите все результаты:

std::vector< std::vector<T> > neighbor_permutations; 
for(int i = 0; i < n; i++) { 
    for(int j = i + 1; j < n; j++) { 
     std::vector<T> perm(v); 
     std::swap(perm[i], perm[j]); 
     neighbor_permutations.push_back(perm); 
    } 
} 

Быстрее версия - не собирать результаты:

for(int i = 0; i < n; i++) { 
    for(int j = i + 1; j < n; j++) { 
     std::swap(v[i], v[j]); 
     process_permutation(v); 
     std::swap(v[i], v[j]); 
    } 
} 

Answer 2

Возможно, это хорошая идея, чтобы разделить ее на две части:

• Как сгенерировать «соседние перестановки»

• Как перебрать их

---

Что касается первого, то легко написать функцию:

std::vector<T> make_neighbor_permutation(
    const std::vector<T> &orig, std::size_t i, std::size_t j); 

меняющего я и J. Я не понял из вашего вопроса, есть ли дополнительное ограничение: j = i + 1, и в этом случае вы можете сбросить параметр.

---

Вооруженный этой функции, теперь нужно итератор, который перебирает все юридические комбинации я и J (опять же, я не уверен в интерпретации вашего вопроса. Может быть, есть n - 1 значения).

Это очень легко сделать, используя boost::iterator_facade. Вам просто нужно определить итератор, который принимает в конструкторе ваш исходный итератор, и устанавливает i (и, возможно, j) в начальные значения. По мере его увеличения необходимо обновить индекс (или индексы).Метод разыменования должен вызывать указанную выше функцию.

Answer 3

Другой способ получить это, просто попробовать.

int main() 
    { 
     std::vector<char> vec={'b','a','c','d'}; 
     std::vector<int> vec_in={1,1,0,0}; 

     do{ 
      auto it =std::find(vec_in.begin(),vec_in.end(),1); 
      if(*(it++) ==1) 
      { 
       for(auto &x : vec) 
       { 
        std::cout<<x<<" "; 
       } 
       std::cout<<"\n"; 
      } 

     } while(std::next_permutation(vec_in.begin(),vec_in.end()), 
       std::next_permutation(vec.begin(),vec.end())); 
    }