Damerau-Damerau distance

Question

Given a list of the integers from \$1\$ to some \$n\$, give the minimum number of adjacent swaps required to put the list in ascending order.

You will receive a list as input and should output a non-negative integer. You may if you wish choose to expect a list of the integers from \$0\$ to \$n\$ instead.

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

Test cases

[3,2,1] -> 3
[1,2,3,4] -> 0
[2,1,3,4] -> 1
[2,1,4,3] -> 2
[2,4,1,3] -> 3
[4,2,3,1] -> 5
[4,3,2,1] -> 6

Answer 1

MATL, 5 4 bytes

-20% thanks to Luis Mendo!

&<Rz

Try it online! or Verify all cases!

As long as the list is not sorted, there is always an adjacent pair that is out of order. Swapping this pair yields an optimal strategy as:

• this swap reduces the number of any pairs that are out of order (not just adjacent) by one.
• no swap can remove two of those pairs.
• the list is sorted when there are no such pairs left.

This means counting the number of unordered pairs gets us the minimum number of swaps to sort:

&< less-than table
R upper triangular matrix
z count the non-zero elements

Answer 2

R, 38 bytes

function(x)sum(combn(c(0,x),2,diff)<0)

Try it online!

Adaptation of ovs's answer. Test harness taken from Dominic van Essen's answer.

combn(x,m) in R generates all size m combinations of the elements of x¹, and has an optional FUN argument which it applies to each of those combinations. As luck would have it, it's implemented in such a way as to maintain the order of elements in x in each of those combinations; for x=c(3,1,4,2):

     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    3    3    3    1    1    4
[2,]    1    4    2    4    2    2

Using FUN=diff results in a vector which contains the upper-triangular part of the matrix of comparisons:

[1] -2  1 -1  3  1 -2

These are negative precisely where there is a swapped pair, so count the negatives.

Unfortunately, R will throw an error for combn(1,2) since it can't get a combination of 2 out of a single value, so 0 is prepended. This has no impact (since the diff will always be positive), and neatly fixes that edge case.

---

¹ If x is a single numeric, it instead uses seq_len(n) which will be 1:floor(n) for n>=1 and an empty vector otherwise. R functions sometimes have weird special cases for length-one inputs.

Answer 3

Factor + koszul, 10 bytes

inversions

Try it online!

Answer 4

Curry (PAKCS), 35 bytes

f(h:t)=length[1|c<-t,c<h]+f t
f[]=0

Try it online!

A port of ovs' MATL answer.

Answer 5

R, 46 bytes

function(x)sum(upper.tri(a<-outer(x,x,`>`))*a)

Try it online!

Uses ovs' approach: upvote that!

Answer 6

Jelly, 6 bytes

Œ¿’Æ!S

A monadic Link that accepts the shuffled list of \$[1,n]\$ and yields the swap count.

Try it online!

How?

Œ¿’Æ!S - Link: list of [1,n] in some order, L
Œ¿     - 1-indexed index of L in a sorted list of all permutations of L
  ’    - decrement -> same but 0-indexed
   Æ!  - convert to factorial number system (mixed-radix base using ..., 2!, 1!, 0!)
     S - sum

---

I think that the method employed by ovs is also six, but perhaps there is a five or better out there. For example:

Œc>/€S

or (counting swapping from the other end):

<";\FS

or

>Ṫ$ƤFS

Answer 7

Nekomata + -n, 3 bytes

Sđ>

Attempt This Online!

A port of the @ovs's MATL answer.

Sđ>
S     Find a subset of the input that
 đ    has exactly two elements where
  >   the first is greater than the second.

-n counts the number of solutions.

Answer 8

Python 3, 69 bytes

port of ovs' MATL answer

lambda n:sum(a>b for a,b in combinations(n,2))
from itertools import*

Try it online!

Answer 9

Python, 47 bytes (@dingledooper)

f=lambda P,*s:s>()and sum(P>Q for Q in s)+f(*s)

Attempt This Online!

Old Python, 48 bytes

f=lambda P,*s:sum(map(P.__gt__,s),*s and[f(*s)])

Attempt This Online!

Takes the splatted input and returns the inversion number.

Just like @ovs's answer this directly computes the inversion number. It uses recurrence through the optional initial value to the sum function.

This appears to be quite similar to @arnauld's approach (going by comments as I don't read JS).

Answer 10

Vyxal, 11 bytes

Ṙṗ'L2=;vÞṠ∑

Try it Online!

Based on Kendall tau distance definition.

May be golfed more, but I don't like direct ports of another answers, so golfing should be based on the same definition

Answer 11

APL+WIN, 25 bytes

Prompts for vector of integers

+/>/n[⊃(,n∘.<n)/,n∘.,n←⎕]

Try it online! Thanks to Dyalog APL Classic

Answer 12

05AB1E, 6 bytes

δ›Åu˜O

Port of @ovs' MATL answer, so make sure to upvote him as well!

First time I'm using the triangle of a matrix builtin in 05AB1E. :) The ݁u could alternatively be ‹Ål for the same byte-count.

Try it online or verify all test cases.

Explanation:

δ       # Apply double-vectorized, implicitly using the input-list twice:
 ›      #  Check if the first value is larger than the second
        # (this basically creates a larger-than table)
        #  e.g. [2,4,1,3] → [[0,0,1,0],[1,0,1,1],[0,0,0,0],[1,0,1,0]]
  Åu    # Pop and leave the upper triangle of this matrix
        #  → [[0,0,1,0],[0,1,1],[0,0],[0]]
    ˜   # Flatten it to a list
        #  → [0,0,1,0,0,1,1,0,0,0]
     O  # Sum it
        #  → 3
        # (which is output implicitly as result)

Answer 13

JavaScript (ES6), 42 bytes

This is based on ovs' insight.

f=([x,...a])=>x&&a.map(y=>n+=y<x,n=f(a))|n

Try it online!

Commented

f = (         // f is a recursive function taking:
  [x,         //   x = next value from the input list
      ...a]   //   a[] = remaining values
) =>          //
x &&          // abort if x is undefined
a.map(y =>    // otherwise, for each value y in a[]:
  n += y < x, //   increment n if y is less than x
  n = f(a)    //   initialize n to the result of a recursive call
)             // end of map()
| n           // return n (coerced to 0 if undefined)

Answer 14

C (gcc), 61 bytes

c;i;f(a,n)int*a;{for(c=0;n--;)for(i=n;i--;)c+=a[n]<a[i];i=c;}

Try it online!

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Returns the minimum number of adjacent swaps required to put the list in ascending order.

Uses ovs's idea from his MATL answer.

Answer 15

Charcoal, 12 bytes

ＩΣＥθＬΦ…θκ›λι

Try it online! Link is to verbose version of code. Explanation: Being a competent call change conductor, I already how many adjacent swaps I would need to get back to rounds (all bells in ascending order) from any given change (permutation), which is basically the same algorithm everyone else is using anyway.

   θ            Input array
  Ｅ             Map over values
       θ        Input array
      …         Truncated to length
        κ       Current index
     Φ          Filtered where
          λ     Inner value
         ›      Is greater than
           ι    Outer value
    Ｌ           Take the length
 Σ               Take the sum
Ｉ                Cast to string
                 Implicitly print

Answer 16

PARI/GP, 35 bytes

a->sum(i=1,#a,sum(j=1,i,a[i]<a[j]))

Attempt This Online!

A port of ovs' MATL answer.

Answer 17

Retina 0.8.2, 33 bytes

\d+
$*
+`(1+(1+)#*),\2\b
$2,$1#
#

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

(1+(1+)#*),\2\b
$2,$1#

Swap two adjacent numbers if the first is bigger, and mark that a swap took place.

+`

Make as many swaps as possible.

#

Count the number of swaps.

Answer 18

Arturo, 36 bytes

$=>[combine.by:2&|enumerate=>[<do&]]

Try it

$=>[               ; a function
    combine.by:2&  ; get all pair combinations in input
    |              ; then
    enumerate=>[   ; count how many pairs
        <do&       ; are unsorted
    ]              ; end enumerate
]                  ; end function

Answer 19

Pyt, 12 bytes

Đɐ>ĐŁřĐɐ≤*ƑƩ

Try it online!

Đ                  implicit input; Đuplicate
 ɐ>                for ɐll possible pairs, is the first element greater than the second?
   Đ               Đuplicate
    Ł              get Łength
     ř             řangify
      Đ            Đuplicate
       ɐ≤          for ɐll possible pairs, is the first element less than or equal to the second?
         *         element-wise multiplication
          Ƒ        Ƒlatten
           Ʃ       Ʃum; implicit print

Answer 20

Wolfram Language (Mathematica), 52 43 bytes

saved 9 bytes thanks to the comment of @att.

Modified from @alephalpha's answer

---

Try it online!

Sum[Boole[#[[0;]]<#[[j]]],{,Tr[1^#]},{j,}]&

---

In this problem, you need to calculate the inversion number of a permutation.

Answer 21

Retina, 22 bytes

\d+
*
rw`\1\b.*,(_+)\b

Try it online! Link includes test cases. Explanation: The first stage simply converts to unary. The second stage then counts the number of overlapping matches (w) where the first number is not less than the second number. The r flag causes the match to be processed right-to-left, so the second number is matched first and the first number then compared against it; if left-to-right matching was used, either the input would have to be reversed, or a negative lookahead used to ensure the second number is less than the first, either way costing more bytes.