Timeline for Permutation generation problem using swaps
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8 at 20:30 | comment | added | Per Alexandersson | 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. | |
| Feb 22 at 18:01 | comment | added | Steven Stadnicki | 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. | |
| Feb 22 at 17:49 | comment | added | Mohammad Al-Turkistany | @StevenStadnicki Yes, that is a possibility. Also, a pair of 2-elements tuple may share a single index. | |
| Feb 22 at 17:44 | comment | added | Steven Stadnicki | 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? | |
| Feb 22 at 16:28 | history | asked | Mohammad Al-Turkistany | CC BY-SA 4.0 |