8
\$\begingroup\$

Task

Given a finite permutation output its inverse.

You may take input and output in any reasonable format equivalent to a list of natural numbers. You may choose to use 0 indexing or 1 indexing. Your input and output format should be the same. You may assume a permutation has at least 1 element.

This is so the goal is to minimize the size of your source as measured in bytes.

Permutations

A finite permutation is a function which takes an \$n\$-tuple and produces an \$n\$-tuple such that every element of the input is present in the output, and the ordering does not rely on the values of the inputs.

We can unambiguously represent these permutations with an \$n\$-tuple where each element is the index of where it will end up. For example:

$$ (3 \,\, 2 \,\, 1 \,\, 0) $$

This permutation reverses a \$4\$ element tuple. The first element goes to the 3rd (last) position, the second goes to the 2nd (penultimate) position etc.

With this representation a valid permutation is just any list of size \$n\$ which contains the numbers \$0\$ through \$n-1\$.

For a permutation \$A\$ the inverse permutation of \$A\$ is a permutation such that when applied after \$A\$ it restores the list to it's initial state.

For example \$(3\,\,2\,\,1\,\,0)\$ is the permutation that reverse the order of 4 elements. It is its own inverse since reversing twice gets you back to where you started. \$(1\,\,2\,\,3\,\,4\,\,0)\$ takes the first of 5 elements and moves it to the end, it has an inverse of \$(4\,\,0\,\,1\,\,2\,\,3)\$ since that takes the last of 5 elements and moves it to the front:

$$ (A,B,C,D,E) \\ \underset{\,(1\,\,2\,\,3\,\,4\,\,0)\,}{\xrightarrow{}}\\ (B,C,D,E,A) \\ \underset{\,(4\,\,0\,\,1\,\,2\,\,3)\,}{\xrightarrow{}}\\ (A,B,C,D,E) $$

Every permutation has an inverse.

Test cases

[0] -> [0]
[0,1,2] -> [0,1,2]
[2,1,0] -> [2,1,0]
[1,2,0] -> [2,0,1]
[0,2,1] -> [0,2,1]
[1,2,0,5,4,3] -> [2,0,1,5,4,3]
Improve this question
\$\endgroup\$
8
  • 2
    \$\begingroup\$ A bit surprised I couldn't find this question already. If someone does, let me know and I'll be happy to close this. \$\endgroup\$
    – Wheat Wizard ♦
    Commented Feb 26, 2022 at 12:49
  • 4
    \$\begingroup\$ Does this answer your question? codegolf.stackexchange.com/questions/136637/… \$\endgroup\$
    – chunes
    Commented Feb 26, 2022 at 14:03
  • 6
    \$\begingroup\$ Does this answer your question? Get the indices of an array after sorting \$\endgroup\$
    – pxeger
    Commented Feb 26, 2022 at 14:20
  • 2
    \$\begingroup\$ @pxeger I'm tempted to say yes. But that is more general seeing as it's not restricted to permutations. If you have a builtin that does that, it works here. But if you don't have a way to sort by indices, or to sort at all there are other viable approaches that exploit the restrictions to permutations. Sorting can be pretty expensive if you don't have a built in and this challenge doesn't require sorting. \$\endgroup\$
    – Wheat Wizard ♦
    Commented Feb 26, 2022 at 14:24
  • 1
    \$\begingroup\$ Also compare the two python (without numpy) approaches. Since this one has a uniqueness guarantee it can be a lot shorter. \$\endgroup\$
    – Wheat Wizard ♦
    Commented Feb 26, 2022 at 14:26

20 Answers 20

Reset to default
5
\$\begingroup\$

R, 5 bytes

order

Try it online!

R, 26 bytes

function(x)match(seq(x),x)

Try it online!

Both 1-indexed.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 28 bytes

Modifies the input list in-place.

a=>[...a].map((v,i)=>a[v]=i)

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

MATL, 2 bytes

&S

Try it online!

Built-in, 1-indexed.

Get the second output of sort. Implicit input, implicit output.

MATL, 4 bytes

fG&m

Try it online!

Just to make use of the "restricted to permutations" aspect of this question (mentioned in the question comments). Construct an array of 1:length(input), and find the position of each element of that in the input array.

Another option at 6 bytes: t"X@@(

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 8 bytes

Ordering

Try it online! 1-indexed (while the input can be either 0- or 1-indexed, the output is always 1-indexed). Plot twist: this generic builtin beats the specific builtin InversePermutation (not to mention that that builtin operates on Mathematica's custom permutation type, which would be hard to justify as being "equivalent to a list of natural numbers").

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K (ngn/k), 7 1 bytes

<

built in.
old answer {x?!#x}

Try it online!

Explanation

{x?!#x}   a function that takes a list x
 x?       indices of the elements in x
   !#x    in the range to length x
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 35 31 bytes

lambda l:map(l.index,sorted(l))

Try it online!

Thanks to Jonathan Allan for the -4 bytes!

Improve this answer
\$\endgroup\$
2
  • 3
    \$\begingroup\$ range(len(l)) can be sorted(l) for -4. \$\endgroup\$
    – Jonathan Allan
    Commented Feb 26, 2022 at 13:43
  • \$\begingroup\$ This answer hurts me emotionally, as I fear seeing it in production code despite it having quadratic performance. \$\endgroup\$
    – Don Hatch
    Commented Nov 2 at 19:41
2
\$\begingroup\$

Python 3 NumPy (not using builtin), 23 bytes

lambda L:L.put(L[L],+L)

Try it online!

Expects a numpy array and modifies it in-place.

Python 3 NumPy (not using builtin), 29 bytes

lambda L:sorted(L,key=L.item)

Try it online!

This doesn't really use numpy except for the shorter item member which replaces the cumbersome __getitem__

Python 3 NumPy (builtin), 20 bytes

lambda L:L.argsort()

Try it online!

This one requires the input to be a numpy array.

Python 3 NumPy (builtin), 26 bytes

from numpy import*
argsort

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Sorry if I'm missing something obvious, but... what do "NumPy (not using builtin)" and "NumPy (builtin)" mean? \$\endgroup\$
    – Don Hatch
    Commented Nov 3 at 8:00
1
\$\begingroup\$

Builtin solutions

APL / BQN, 1 byte

⍋

Try it on APLgolf! / Run with BQN!

J, 2 bytes

/:

Try it online!

Jelly, 1 byte

Ụ

Try it online! (1-indexed)

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Factor, 8 bytes

arg-sort

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 16 bytes

p->vecsort(p,,1)

Try it online!

Improve this answer
\$\endgroup\$
1
1
\$\begingroup\$

Retina 0.8.2, 56 bytes

\d+
$*
(?<=(?=(1*,)*(?<-2>1)*(?(2)^)(?!1))^(1*,)*)1*
$#1

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

1*

For each element...

(?<=^(1*,)*)

... find its index, ...

(?=(1*,)*(?<-2>1)*(?(2)^)(?!1))

... then find the index of the element with that as its value.

$#1

Replace the element with that index (in decimal).

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 8 bytes

sortperm

Try it online!

1-indexed

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

flax, 1 byte

⍋

Builtin \o/

Unlike Jelly, flax is 0-indexed.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Desmos, 20 bytes

f(l)=sort(sort(l),l)

Try It Desmos!

Try It Desmos! - Prettified

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I believe you can remove the last parentheses ). \$\endgroup\$
    – zoomlogo
    Commented Feb 27, 2022 at 13:42
  • \$\begingroup\$ @PyGamer0 No, it gives an error. \$\endgroup\$
    – Aiden Chow
    Commented Feb 27, 2022 at 23:59
1
\$\begingroup\$

x86-64 machine code, 11 bytes

8B 04 96 89 14 87 FF CA 79 F6 C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as an array of 32-bit integers; the address of the given permutation, as an array of 32-bit integers, in RSI; and the length of that array in EDX. The starting point is after the first 6 bytes.

In assembly:

r:  mov eax, [rsi+4*rdx]    # Load the entry at index EDX into EAX.
    mov [rdi+4*rax], edx    # Store the value of EDX into the result array at index EAX.
f:  dec edx     # (Start here.) Count down from the length in EDX.
    jns r       # Jump back if it isn't negative. (This will iterate from n-1 to 0.)
    ret         # Return.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 2 bytes

{k

0-based.

Try it online or verify all test cases.

Explanation:

{   # Sort the (implicit) input-list
 k  # Get the 0-based indices of each value in the (implicit) input-list
    # (after which the list is output implicitly as result)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Haskell, 43 bytes

import Data.List
f p=snd<$>sort(zip p[0..])

Try it online!

Alternative 47 bytes using association list.

  • saved 7 Bytes thanks to @Unrelated String
  • added a maybe() to convert maybe int to just int, if a just int is acceptable it can be 37 Bytes.
f p|i<-zip p[0..]=maybe 0id.(`lookup`i).snd<$>i

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ -7 on the second version? \$\endgroup\$
    – Unrelated String
    Commented Feb 28, 2022 at 18:10
  • 1
    \$\begingroup\$ Nice one @Unrelated String , although Idk if a just int is valid I thought it was interesting to add that \$\endgroup\$
    – AZTECCO
    Commented Mar 1, 2022 at 7:35
1
\$\begingroup\$

Python3, 27 bytes

def f(l):return l.argsort()

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$
    – rydwolf
    Commented Mar 3, 2022 at 3:40
  • \$\begingroup\$ This seems a bit misleading, since l has to be a numpy.array rather than a python list. \$\endgroup\$
    – Don Hatch
    Commented Nov 2 at 19:30
0
\$\begingroup\$

Vyxal, 1 byte

⇧

Try it Online!

I suppose grading the list up also works.

Vyxal, 9 bytes

Ṗ'2(?~İ)⁼

Try it Online!

Explained

Ṗ'2(?~İ)⁼
Ṗ         # From all permutations of the input
 '        # Keep those where
  2(      #   Getting the result of
   ?~İ    #   [input[x] for x on tos]
      )   #   twice
       ⁼  #   equals the original item.
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 6 bytes

ＩＥθ⌕θκ

Try it online! Link is to verbose version of code. Explanation:

  θ     Input array
 Ｅ      Map over elements
   ⌕    Find index of
     κ  Current index
    θ   In input array
Ｉ       Cast to string
        Implicitly print
Improve this answer
\$\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.