Keeping track of permutations that differ only adjacent pairwise in output of std::next_permutation

  algorithm, c++, permutation

Consider the code snippet:

#include <vector>
#include <algorithm>
#include <stdio.h>
int main(){
     int szvec = 4;
     std::vector<int> vecint(szvec);
     for (size_t i = 0, szi = szvec; i < szi; i++){
         vecint[i] = i;
     }
     do{
         for (size_t i = 0, szi = vecint.size(); i < szi; i++){
             printf("%dt", vecint[i]);
         }
         printf("n");
     } while (std::next_permutation(vecint.begin(), vecint.end()));
}

The output of this is the set of 4! different permutations.:

0       1       2       3   (Permutation 1)
0       1       3       2   (Permutation 2)
0       2       1       3
0       2       3       1
0       3       1       2
0       3       2       1
1       0       2       3
1       0       3       2
1       2       0       3
1       2       3       0
1       3       0       2
1       3       2       0
2       0       1       3
2       0       3       1
2       1       0       3   (Permutation 15)
2       1       3       0
2       3       0       1
2       3       1       0
3       0       1       2
3       0       2       1
3       1       0       2
3       1       2       0
3       2       0       1   (Permutation 23)
3       2       1       0   (Permutation 24)

I am interested in constructing an undirected graph with 24 nodes, (each node represents one permutation), with an edge connecting i and j if these permutations differ from each other in exactly one contiguous pair of elements. For instance, Permutation 1 and Permutation 2 will be connected since they differ in the pairwise exchange over contiguous indices. Permutation 1 and Permutation 15 will NOT be connected since even though they differ in pairwise exchange of elements, this exchange is not over contiguous indices. Permutation 23 and Permutation 24 will be connected.

The only way I can think of now of how to do this is to select each pair of permutations and evaluate explicitly whether they should be connected. Is there a more efficient way of doing this analytically? What I mean by analytical here is that given a particular node i, can we efficiently enumerate all other permutations it will be connected to? Note that szvec can be an arbitrary integer, not only 4.

Source: Windows Questions C++

LEAVE A COMMENT