# Generating permutations with a given bubblesort distance

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.

• 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. – Yuval Filmus Nov 9 '19 at 16:07
• 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... – mmm Nov 9 '19 at 18:16