3
$\begingroup$

I'm looking for an algorithm to randomly generate permutations on 1:n, which though have a defined bubblesort distance d from 1:n, e.g. (2,3,1) and (3,1,2) are distance 1 from (1,2,3), (2,3,1) and (3,1,2) are d=2, finally (3,2,1) is d=3.

Naive approach is to flip a random sorted pair d times, however it seems it does not produce an uniform sample... The exact approach (generate all permutations at a given d and then sample) does not scale too well.

Improve this question
$\endgroup$
  • $\begingroup$ Can you count the number of permutations at a given distance? If so, you can try the approach in this question. While the question is about unranking (given an index $i$, output the $i$'th object in some collection), you can easily convert it to a random generation algorithm by choosing the index uniformly at random. $\endgroup$ – Yuval Filmus Nov 9 '19 at 16:07
  • $\begingroup$ Thanks; turns out the counts of permutation at each distance form the Mahonian number triangle, which made me realise I'm looking to generate random permutation with a given number of inversions. And GitHub has the code. Time to understand what it does... $\endgroup$ – mmm Nov 9 '19 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.