11
\$\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\$
6
  • 1
    \$\begingroup\$ I suspect there's a parity argument of some sort... \$\endgroup\$
    – emanresu A
    Jul 27, 2022 at 10:38
  • 9
    \$\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, 2022 at 10:46
  • 8
    \$\begingroup\$ Alternatively, these are all even-signed permutations of the reverse of the list. \$\endgroup\$
    – xnor
    Jul 27, 2022 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\$ Jul 27, 2022 at 17:44
  • 1
    \$\begingroup\$ My observation about where the even permutations are in the list of permutations that Jelly's Œ! produces was incorrect. \$\endgroup\$ Sep 3, 2022 at 20:25

7 Answers 7

6
\$\begingroup\$

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

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

\$\endgroup\$
2
  • \$\begingroup\$ This approach doesn't seem to work when the original list is not sorted. \$\endgroup\$
    – xigoi
    Apr 22, 2023 at 12:49
  • 1
    \$\begingroup\$ @xigoi Thanks. Fixed for +13 bytes. \$\endgroup\$
    – chunes
    Apr 22, 2023 at 15:35
3
\$\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
3
\$\begingroup\$

Vyxal, 13 bytes

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

Try it Online!

Port of Jonathan Allan's new Jelly answer.

\$\endgroup\$
0
2
\$\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 36 bytes

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

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

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

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.

EΦυ¬﹪κ²⭆¹ι

Pretty-print only the even permutations.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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