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() 那么我将得到所有可能的排列，而不仅仅是 "neighbor" 那些...

您知道如何实现吗？

Answer 1

最初，我想过滤 hamming distance 大于 2 的排列。

但是，如果您真的只需要生成交换一对产生的所有向量，那么这样做会更有效率：

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

根据你是否需要收集所有的结果，你应该在交换之前复制或向量，或者在处理完当前排列后再次交换i和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

也许把它分成两部分是个好主意：

如何生成"neighbor permutations"
如何迭代它们

关于第一个，写个函数很简单：

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

交换 i 和 j。我不明白你的问题是否有额外的约束 j = i + 1，在这种情况下你可以删除一个参数。

有了这个函数，您现在需要一个迭代器来遍历 i 和 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()) );
    }

C ++遍历所有邻居排列

c++ iterate through all neighbor permutations

c++

permutation