CGAC2022 Day 6: Shuffles with specific "magic number"

Question

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

Answer 1

J, ²⁶ 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.

Answer 2

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!

Answer 3

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.

Answer 4

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\$.

Try it online or verify all test cases.

Equal bytes alternative actually performing swaps:

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

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

Try it online or verify all test cases.

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)

Answer 5

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.

≔⟦⟧υ

Start with no permutations for the next magic number.

ＦθＦＬκＦ

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.

Answer 6

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.

Answer 7

JavaScript (Node.js), 83 bytes

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

Try it online!

Answer 8

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]])
    $                 - last two links as a monad - f(x=that):
   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:
                  ḟ   -   filter-discard
                    Q - deduplicate

Answer 9

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