# Damerau-Damerau distance

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

• Related: swap to sort an array (differences: takes a list with potential duplicated items; can swap from anywhere instead of just adjacent, making it a lot harder; and you output the index-pairs instead of the amount of swaps necessary - so probably not too useful now that I think about it). Mar 31, 2022 at 13:32
• What does "Damrau-Damrau" actually mean? I can't find any evidence of the name "Damrau-Damrau distance" Mar 31, 2022 at 16:09
• @pxeger Damerau-Levenshtein distance is Levenshtein distance with swaps, so Damerau-Damreau is Damerau-Levenstein without Levenshtein, i.e. just swaps. Mar 31, 2022 at 17:47

# MATL, 5 4 bytes

-20% thanks to Luis Mendo!

&<Rz


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

# R, 38 bytes

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


Try it online!

combn(x,m) in R generates all size m combinations of the elements of x1, 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:

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

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

# Factor + koszul, 10 bytes

inversions


Try it online!

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

# R, 46 bytes

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


Try it online!

Uses ovs' approach: upvote that!

• I was in the middle of suggesting a 1-byte golf using * instead of [] but seems you beat me to it! Mar 31, 2022 at 15:45
• 33 bytes Mar 31, 2022 at 15:54
• Actually, I think it should be 38 bytes, thanks to the special case of length-one input. Mar 31, 2022 at 15:56
• @Giuseppe - That's completely different, and really good. Post it! Mar 31, 2022 at 17:00

# 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  # 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. # 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! # 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). • I think the "simpler" list comprehension saves a byte here: f=lambda x,*a:a>()and sum(x>y for y in a)+f(*a) Mar 31, 2022 at 21:14 # 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 # APL+WIN, 25 bytes Prompts for vector of integers +/>/n[⊃(,n∘.<n)/,n∘.,n←⎕]  Try it online! Thanks to Dyalog APL Classic # 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. 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],] ˜ # 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)  # 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)  # 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. # 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  # 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. # 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. # 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


# 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


# Wolfram Language (Mathematica), 52 43 bytes

saved 9 bytes thanks to the comment of @att.

Try it online!

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


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

• -9
– att
Apr 11 at 0:40

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