Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
On the flight to Hawaii for vacation, I'm playing with a deck of cards numbered from 1 to \$n\$. Out of curiosity, I come up with a definition of "magic number" for a shuffled deck:
- The magic number of a shuffle is the minimum number of swaps needed to put the cards back into the sorted order of 1 to \$n\$.
Some examples:
[1, 2, 3, 4]
has magic number 0, since it is already sorted.[4, 3, 2, 1]
has magic number 2, since I can swap (1, 4) and then (2, 3) to sort the cards.[3, 1, 4, 2]
has magic number 3. There is no way I can sort the cards in fewer than 3 swaps.
Task: Given \$n\$ and the magic number \$k\$, output all permutations of \$n\$ whose magic number is \$k\$.
You may assume \$n \ge 1\$ and \$0 \le k < n\$. You may output the permutations in any order, but each permutation that satisfies the condition must appear exactly once. Each permutation may use numbers from 0 to \$n-1\$ instead of 1 to \$n\$.
Standard code-golf rules apply. The shortest code in bytes wins.
Trivia: The number of permutations for each \$(n, k)\$ is given as A094638, which is closely related to Stirling numbers of the first kind A008276.
Test cases
n, k -> permutations
1, 0 -> [[1]]
2, 0 -> [[1, 2]]
2, 1 -> [[2, 1]]
3, 0 -> [[1, 2, 3]]
3, 1 -> [[1, 3, 2], [2, 1, 3], [3, 2, 1]]
3, 2 -> [[3, 1, 2], [2, 3, 1]]
4, 0 -> [[1, 2, 3, 4]]
4, 1 -> [[1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 3, 2], [2, 1, 3, 4],
[3, 2, 1, 4], [4, 2, 3, 1],
4, 2 -> [[1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4],
[2, 4, 3, 1], [3, 1, 2, 4], [3, 2, 4, 1], [3, 4, 1, 2],
[4, 1, 3, 2], [4, 2, 1, 3], [4, 3, 2, 1]]
4, 3 -> [[2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 2, 1],
[4, 1, 2, 3], [4, 3, 1, 2]]