7
\$\begingroup\$

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ I suspect there's a parity argument of some sort... \$\endgroup\$
    – emanresu A
    Jul 27 at 10:38
  • 6
    \$\begingroup\$ 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 \$\endgroup\$
    – xnor
    Jul 27 at 10:46
  • 5
    \$\begingroup\$ Alternatively, these are all even-signed permutations of the reverse of the list. \$\endgroup\$
    – xnor
    Jul 27 at 10:53
  • 1
    \$\begingroup\$ You should probably specify that \$P\$ is the set of all pairs of positions \$(i,j)\$ where \$i<j\$. \$\endgroup\$
    – Adam
    Jul 27 at 17:44

7 Answers 7

5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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, Œ!.

ṚŒ!m4ÐƤ3Ẏ - Link: list, L
Ṛ         - 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
\$\endgroup\$
0
3
\$\begingroup\$

Vyxal, 14 9 bytes

ṘṖ4ẇ3vḞÞf

Try it Online!

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

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
0
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 86 bytes

≔Eθ⁰η≔¹ζ⊞υ⮌θW‹ζLη¿‹§ηζζ«≔∧﹪沧ηζε≔§θεδ§≔θε§θζ§≔θζδ§≔ηζ⊕§ηζ≔¹ζ⊞υ⮌θ»«§≔ηζ⁰≦⊕ζ»EΦυ¬﹪κ²⭆¹ι

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.

≔Eθ⁰η

Start with a "stack" of zeros.

≔¹ζ

Initialise the "stack pointer".

⊞υ⮌θ

Include the null permutation of the reversed input.

W‹ζLη

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

»EΦυ¬﹪κ²⭆¹ι

Pretty-print only the even permutations.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.