CODEWITHSUNDEEP
c++permutation
Arcyno
Arcyno

Reputation: 4603

c++ iterate through all neighbor permutations

I have a vector of N objects, and I would like to iterate through all neighbor permutations of this vector. What I call a neighbor permutation is a permutation where only two elements of the original vector would be changed : if I have a vector with 'a','b','c','d' then :

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

If I use std::next_permutation(myVector.begin(), myVector.end() then I will get all the possible permutations, not only the "neighbor" ones...

Do you have any idea how that could be achieved ?

Upvotes: 1

Views: 1211

Answers (3)

Steephen
Steephen

Reputation: 15844

Another way to get it, just a try.

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

Upvotes: 0

fferri
fferri

Reputation: 18950

Initially, I thought I would filter the permutations that have a hamming distance greater than 2.

However, if you really only need to generate all the vectors resulting by swapping one pair, it would be more efficient if you do like this:

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

Depending on whether you need to collect all the results or not, you should make a copy or the vector before the swap, or swap again i and j after you processed the current permutation.

Collect all the results:

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

Faster version - do not collect results:

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

Upvotes: 2

Ami Tavory
Ami Tavory

Reputation: 76406

Perhaps it's a good idea to divide this into two parts:

  • How to generate the "neighbor permutations"

  • How to iterate over them

Regarding the first, it's easy to write a function:

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

which swaps i and j. I did not understand from your question if there's an additional constraint that j = i + 1, in which case you could drop a parameter.

Armed with this function, you now need an iterator that iterates over all legal combinations of i and j (again, I'm not sure of the interpretation of your question. It might be that there are n - 1 values).

This is very easy to do using boost::iterator_facade. You simply need to define an iterator that takes in the constructor your original iterator, and sets i (and possibly j) to initial values. As it is incremented, it needs to update the index (or indices). The dereference method needs to call the above function.

Upvotes: 1

Related Questions