Swap every two elements in the list every possible way

Question

Inspired by this question.

Challenge

Let L be a list of n distinct elements. Let P be the set of all (unordered) pairs of positions in P. Let R be a result of applying a pair-swap operation on L by every pair in P in any order.

Example:
L = [1, 7, 8]
P = {(1, 2), (0, 1), (0, 2)}
L = [1, 7, 8] -> [1, 8, 7] -> [8, 1, 7] -> [7, 1, 8] = R

Your task is to output every possible R (without multiplicity) in any order.

Constraints

• L can have any length, including 0 and 1
• All elements of L are guaranteed to be distinct

Examples

1. Input: [1, 5]
   Output: [5, 1]
2. Input: [0, 1, 2, 3]
   Output:
   [3, 2, 1, 0]
[1, 0, 3, 2]
[2, 3, 0, 1]
[3, 0, 2, 1]
[1, 2, 0, 3]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 1, 3, 0]
[0, 2, 3, 1]
[3, 1, 0, 2]
[0, 3, 1, 2]
[0, 1, 2, 3]
3. Input: [150]
   Output: [150]

Rules

• this is code-golf challenge, so the shortest code wins
• standard rules apply for your answer with default I/O rules
• default Loopholes are forbidden.

Answer 1

Jelly, 13 bytes

ŒcżU$Œ!y@ƒ€⁸Q

Try it online!

How?

Since the elements are guaranteed to be distinct we can swap pairs of elements rather than elements at pairs of indices and otherwise follow the description in the question.

ŒcżU$Œ!y@ƒ€⁸Q - Link: list of distinct integers, L
                                e.g. [1,7,8]
Œc            - pairs           [[1,7],[1,8],[7,8]]
    $         - last two links as a monad:
   U          -   upend         [[7,1],[8,1],[8,7]]
  ż           -   zip           [[[1,7],[7,1]],[[1,8],[8,1]],[[7,8],[8,7]]]
     Œ!       - all permutations
          €   - for each:
         ƒ ⁸  -   reduce by, starting with L:
        @     -     with swapped arguments:
       y      -       translate
            Q - deduplicate

Answer 2

Factor + koszul math.combinatorics, 60 52 65 bytes

[ natural-sort [ reverse inversions even? ] filter-permutations ]

Try it online!

Uses the following observation by @xnor: "Alternatively, these are all even-signed permutations of the reverse of the list." (Although I found it actually seems to be the reverse of each permutation of the list, not the reverse of the list.)

Answer 3

05AB1E, 17 13 bytes

œʒRøãε`›`›}OÈ

-4 bytes thanks to @chunes' corrected version of @xnor's insight: "These are all even-signed reversed permutations of the list."

Try it online or verify all test cases.

Explanation:

øãε`›`›}O is taken from my 05AB1E answer in the related "Parity of a Permutation" challenge (which could alternatively be øDδ›Æ0›˜O for the same byte-count).

œ           # Get all permutations of the (implicit) input-list
 ʒ          # Filter it by:
  R         #  Reverse the current permutation
   ø        #  Create pairs with the (implicit) input-list
    ã       #  Cartesian product of itself to get a list of all pairs of pairs
     ε      #  Map each pair of pairs to:
      `     #   Pop and push the pairs separately to the stack
       ›    #   Vectorized larger than check: [a,b] and [c,d] → [a>c,b>d]
        `   #   Pop and push the pairs separated to the stack again
         ›  #   Larger than check again: a>c and b>d → (a>c)>(b>d)
     }O     #  After the map: sum to get get the amount of truthy values
       È    #  Check if this sum is even
            # (after which the filtered list is output implicitly)

Answer 4

Vyxal, 13 bytes

2ḋṖƛ?$(nnṘĿ;U

Try it Online!

Port of Jonathan Allan's new Jelly answer.

Answer 5

JavaScript (V8), 76 bytes

This is based on xnor's insight.

f=(a,k,...p)=>a.map((v,i)=>f(a.filter(_=>i--),i-~k,...p,v))+a||k&1||print(p)

Try it online!

Answer 6

Python, 124 121 bytes

def p(a,k=0,t=0):
 if a[(i:=k):]:
  while a[i:]:c=[*a];c[k],c[i]=c[i],c[k];p(c,k+1,t+(i>k));i+=1
 elif~t%2:print(a[::-1])

Attempt This Online!

Answer 7

Charcoal, 86 36 bytes

⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻⎇﹪λ²⮌θθκ⁺κ⟦μ⟧υＥΦυ¬﹪κ²⭆¹ι

Attempt This Online! Link is to verbose version of code. Explanation:

⊞υ⟦⟧Ｆθ≔ΣＥυＥ⁻⎇﹪λ²⮌θθκ⁺κ⟦μ⟧υ

Generate all the permutations of the input, alternating between even and odd permutations. This is based on my answer to Hankel transform of an integer sequence but operates directly on the input instead of a range. This works because the elements in the input are guaranteed to be unique.

ＥΦυ¬﹪κ²⭆¹ι

Pretty-print only the even permutations.