4
$\begingroup$

This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.

We're given as input a "target permutation" $\sigma\in S_n$, as well as an list of pairs of indices $[i_1,i_2], \ldots, [i_{2k-1},i_{2k}],\ldots,[i_{m-1}, i_m]$. Starting with the list $(1,2,\ldots,n)$, pair $[i_{2k-1}, i_{2k}]$ swaps the elements at positions $i_{2k-1}$ and $i_{2k}$. Indices $i_1, i_2, \dots, i_m$ are not necessarily distinct.

Can we generate the target permutation by applying the given swaps in some order? Each swap must be used exactly once, so this is different from testing membership in a permutation group.

Is this problem NP-complete? Is it efficiently solvable?

This was asked on TCS SE without getting any answer

Improve this question
$\endgroup$
4
  • $\begingroup$ When you say that the indices are not necessarily distinct, do you mean that the sequence $\{[i_1, j_1], [i_2, j_2], \ldots\}$ of available swaps (changing your notion slightly) is potentially a multiset rather than a set? $\endgroup$
    – Steven Stadnicki
    Commented Feb 22 at 17:44
  • $\begingroup$ @StevenStadnicki Yes, that is a possibility. Also, a pair of 2-elements tuple may share a single index. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 22 at 17:49
  • 3
    $\begingroup$ The problem is very boring if you don't allow pairs to share an index! Then there's only one permutation that can be generated, the product of all the individual two-cycles in your list. $\endgroup$
    – Steven Stadnicki
    Commented Feb 22 at 18:01
  • $\begingroup$ One obvious check is that the parity of number of inversions in the target, must match the number of swaps (if all are to be used). Perhaps one can model this in practice by some type of search in the set of permutations using some type of heuristic? I.e, first only consider swaps to make the lowest number be ok, and then proceed inductively. $\endgroup$
    – Per Alexandersson
    Commented Mar 8 at 20:30

0

Reset to default

You must log in to answer this question.