# CGAC2022 Day 6: Shuffles with specific "magic number"

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 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 -> []
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]]

• Related: swap to sort an array. Although this challenge is definitely an easier subset, since you know you're working with a $[1,n]$-ranged list and know the number of swaps $k$ here. Dec 6, 2022 at 9:31

# J, 26 22 bytes

((=#"1-#@C.)#])!A.&i.]


Try it online!

-4 thanks to Bubbler!

Generates all perms, converts to cycle representation, take sum of "length of each cycle - 1" (this gives number of swaps needed to sort), then filter to only those elements whose swap count matches the input requirement.

• sum of (length of each cycle - 1) = (sum of length of each cycle) - (cycle count) = n - cycle count, so ((=#"1-#@C.)#])!A.&i.] works at 22 bytes. Dec 6, 2022 at 1:14
• Excellent, thx! Dec 6, 2022 at 1:19

# Python 3, 108 bytes

f=lambda n,k,*a:n and sum([f(n-1,k-1,v,*a[:i],n,*a[i+1:])for i,v in enumerate(a)],f(n-1,k,n,*a))or[a]*(k==0)


Try it online!

# Python, 97 bytes

f=lambda n,k:[[]][n+k*k:]or[L[:j]+[n]+(2*L[j:])[1:n-j]for j in range(n)for L in f(n-1,k-(-~j<n))]


Attempt This Online!

### Python, 134 bytes

def f(n,k,L=0):
z=range(n);L=[*(L or z)];n-=1;s=L[n]
for j in z:L[n]=L[j];L[j]=s;yield from([L][n-j:],f(n,k-(j<n),L))[k>0];L[j]=L[n]


Attempt This Online!

Enumerates the magic permutations. n is number of elements, k is magic number.

### How?

A modification of a textbook (I'd think) permutation enumerator: go from rightmost to leftmost position swapping each with any position to its left or not at all. All we are adding is fixing the number of swaps.

# 05AB1E, 29 bytes

Lœʒāøœ€.œ€.Δε˜Á2ô€ËP}P}€g<OQ


Port of @Jonah's J answer, but without cyclic permutation builtin†.

Inputs in the order $$\n,k\$$.

Equal bytes alternative actually performing swaps:

ÝRεULœʒ©ãX.Æε®svyÂ‡}D{Q}à].»K


Inputs also in the order $$\k,n\$$.

Explanation:

L             # Push a list in the range [1, first (implicit) input n]
œ            # Get a list of all its permutations
ʒ           # Filter this list of permutations by:
āøœ€.œ€.Δε˜Á2ô€ËP}P}
#  Get the cyclic permutation of the current permutation-list†:
ā          #   Push a list in the range [1,length] (without popping): [1,n]
ø         #   Pair it together with each value in the current permutation
œ          #   Get all permutations of this list
€         #   Map over each permutation:
.œ       #    Get all partitions
€     #   Flatten it one level down
.Δ         #   Find the first partition of permutation of pairs of the current
#   permutation-list that's truthy for:
ε        #    Map over each part of the partition:
˜       #     Flatten the list of pairs
Á      #     Rotate it once towards the right
2ô    #     Split it back into parts
€Ë  #     Check if the values in each individual pair are the same
P #     Check if this is truthy for all of them (thus it's a cycle)
}P       #    After the map: check if it's truthy for the entire partition
}         #   Close the find_first, resulting in the cyclic permutation
€g       #  Get the length of each inner cycle-list
<      #  Decrease each length by 1
O     #  Take the sum of those
Q    #  Check if it's equal to the second (implicit) input k
# (after which the filtered list of permutations is output implicitly)

Ý             # Push a list in the range [0, first (implicit) input k]
R            # Reverse it to [k,0]
ε           # Map over each value:
U          #  Pop the current value, and store it in variable X
L          #  Push a list in the range [1, second (implicit) input n]
œ         #  Get all permutations of this list
ʒ        #  Filter it by:
©       #   Store the current list in variable ® (without popping)
ã      #   Get all pairs of this list
#   (with duplicates by using cartesian power of 2)
X.Æ   #   Get all X-sized combinations of these pairs
#   (without duplicates by using combinations builtin)
ε       #   Map over each list of pairs:
®      #    Push permuted list ®
s      #    Swap so the current list of pairs is at the top
v     #    For-each over each pair y:
y    #     Push the current pair y
Â   #     Bifurcate it; short for Duplicate & Reverse copy
‡  #     Transliterate it in the list, basically swapping the values
}D{Q  #    After the inner loop: check if the list is sorted
D    #     Duplicate the resulting list with performed swaps
{   #     Sort the copy
Q  #     Check if both lists are the same
}à      #   After the inner map: check if any was truthy
]           # Close both the filter and outer map
.»         # Then left-reduce these lists by:
K        #  Removing lists
# (after which the reduced list of permutations is output implicitly)


# Charcoal, 52 bytes

⊞υ…Ｎ≔υθＦＮ«≔⟦⟧υＦθＦＬκＦ⁻⁻ＥλＥκ§κ⎇⁼πλμ⎇⁼πμλπυθ⊞υμ≔⁺θυθ»Ｉυ


Try it online! Link is to verbose version of code. Explanation:

⊞υ…Ｎ


Start with the identity permutation as the only permutation with magic number 0.

≔υθ


Also set this as the list of permutations seen so far.

ＦＮ«


Loop through the magic numbers.

≔⟦⟧υ


ＦθＦＬκＦ


Loop through the swaps of the permutations seen so far (including the ones whose swaps we've already seen but that's code golf for you).

⁻⁻ＥλＥκ§κ⎇⁼πλμ⎇⁼πμλπυθ


Generate the list of potential new permutations but remove any previously seen (including those already seen for this magic number).

⊞υμ


Append any new permutations for this magic number. (Or I could have just concatenated the lists I guess.)

≔⁺θυθ


Append all of the new permutations for this magic number to the list of those seen so far.

»Ｉυ


Output the permutations for the last magic number processed.

# PARI/GP, 48 bytes

f(n,k)=forperm(n,p,n-k-#permcycles(p)||print(p))


Attempt This Online!

A port of @Jonah's J answer.

# JavaScript (Node.js), 83 bytes

f=(n,k,a=[])=>n--?[f,...a].flatMap((v,i,[...b])=>f(b[b=v,i]=n,k-!!i,b)):k?[]:[a]


Try it online!

# Jelly, 21 bytes

ŒcżU$œcⱮŻ}y@ƒ€€R{Ṛḟ/Q  A dyadic Link that accepts $$\n\$$ on the left and $$\k\$$ on the right and yields a list of those permutations of $$\[1,n]\$$ which require a minimum of $$\k\$$ pairwise swaps to sort. Try it online! ### How? Starting with the sorted deck the code performs all possible (up to rearrangement) swap sequences of lengths $$\j \leq k\$$ then takes those reachable with exactly $$\k\$$ swaps and removes any that were reachable with less. ŒcżU$œcⱮŻ}y@ƒ€€R{Ṛḟ/Q - Link: integer, n; integer, k
Œc                    - unordered pairs (n) (e.g. n=3 -> [[1,2],[1,3],[2,3]])
U                  -   reverse each pair
ż                   -   (x) zip with (that) -> P = [[[a,b],[b,a]],...])
}            - with chain's right argument:
Ż             -   zero range (k) -> [0,1,2,...,k]
Ɱ              - map (across j in that) with:
œc               -   (P) combinations (j) -> all (ordered) length j pair-tuples
{     - with chain's left argument:
R      -   range (n) -> [1,2,3,...n]
€       - for each (list of pair-tuples):
€        -   for each pair-tuple:
ƒ         -     reduce (pair-tuple) starting with (range(n)) using:
@          -       with swapped arguments:
y           -         translate (e.g. [3,1,2] y [[2,3],[3,2]] -> [2,1,3])
Ṛ    - reverse
/  - reduce by:
Q - deduplicate


# Pyth, 29 bytes

LsmmXd_kk.cSQ2b{-F_myF]SQdUhE


Try it online!

### Explanation

L                                define y(b): applies every swap possible to every sequence in b
sm           b                    for all d in b
m     .cSQ2                     for all pairs of unique elements in range(1,n+1), k
Xd_kk                          generate a sequence by swapping the elements of k in d
m      UhE    map d over range(k+1)
yF   d       apply y d times to
]SQ        [range(1,n+1)]
_              reverse this
-F               fold over subtraction (remove all states with fewer flips)
{                 deduplicate
`