# Swap every two elements in the list every possible way

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

• I suspect there's a parity argument of some sort... Jul 27 at 10:38
• It looks like these are always half the possible permutations, the odd-signed permutations when n modulo 4 is 1 or 2, and the even-signed permutations when it's 0 or 3. Related: Parity of a Permutation
– xnor
Jul 27 at 10:46
• Alternatively, these are all even-signed permutations of the reverse of the list.
– xnor
Jul 27 at 10:53
• You should probably specify that $P$ is the set of all pairs of positions $(i,j)$ where $i<j$.
Jul 27 at 17:44

# Factor + koszul math.combinatorics, 60 52 bytes

[ [ 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.)

# Jelly, 9 bytes

ṚŒ!m4ÐƤ3Ẏ

A monadic Link that accepts a list of distinct values and yields a list of lists.

Try it online!

### How?

Uses xnor's observation that the required output is the even permutations of the reverse of the input, and an observation about the order of the result of the all-permutations atom, Œ!.

Ṛ         - reverse of L
Œ!       - all permutations
3  - set the right argument to three
4ÐƤ   - for non-overlapping slices of length four:
m      -   modulo slice - i.e get the first and, if it exists the fourth element
Ẏ - tighten

More of the same length, same idea with tweaks to the method of accessing the even permutations:

ṚŒ!s4m€3Ẏ - split into fours; modulo slice each as above; tighten
ṚŒ!s2Jị"\$ - split into twos; modular-index into each pair with its own index
ṚŒ!ḢṪƭ2ÐƤ - alternate between getting the head and tail of each two

# Vyxal, 14 9 bytes

ṘṖ4ẇ3vḞÞf

Try it Online!

Port of Jelly. Original 14 bytes was from 05AB1E.

# 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."

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)

# 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!

# 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!

# Charcoal, 86 bytes

≔Ｅθ⁰η≔¹ζ⊞υ⮌θＷ‹ζＬη¿‹§ηζζ«≔∧﹪ζ²§ηζε≔§θεδ§≔θε§θζ§≔θζδ§≔ηζ⊕§ηζ≔¹ζ⊞υ⮌θ»«§≔ηζ⁰≦⊕ζ»ＥΦυ¬﹪κ²⭆¹ι

Try it online! Link is to verbose version of code. Explanation: Uses Heap's algorithm (non-recursive version) to alternate between even and odd permutations of the reverse of the input, then outputs just the even permutations.

≔Ｅθ⁰η

≔¹ζ

Initialise the "stack pointer".

⊞υ⮌θ

Include the null permutation of the reversed input.

Ｗ‹ζＬη

Repeat until all permutations have been output.

¿‹§ηζζ«

If this element needs to be swapped, then:

≔∧﹪ζ²§ηζε

Calculate the index that it needs to be swapped with.

≔§θεδ§≔θε§θζ§≔θζδ

Swap the two elements.

§≔ηζ⊕§ηζ

Increment the current "stack" entry.

≔¹ζ

Reset the "stack pointer".

⊞υ⮌θ

Save the reversed permutation.

»«§≔ηζ⁰≦⊕ζ

Otherwise, clear this "stack" entry and increment the "stack pointer".

»ＥΦυ¬﹪κ²⭆¹ι

Pretty-print only the even permutations.