17
\$\begingroup\$

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
\$\endgroup\$
3
  • 2
    \$\begingroup\$ 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). \$\endgroup\$ Mar 31, 2022 at 13:32
  • 2
    \$\begingroup\$ What does "Damrau-Damrau" actually mean? I can't find any evidence of the name "Damrau-Damrau distance" \$\endgroup\$
    – pxeger
    Mar 31, 2022 at 16:09
  • 4
    \$\begingroup\$ @pxeger Damerau-Levenshtein distance is Levenshtein distance with swaps, so Damerau-Damreau is Damerau-Levenstein without Levenshtein, i.e. just swaps. \$\endgroup\$
    – Wheat Wizard
    Mar 31, 2022 at 17:47

21 Answers 21

12
\$\begingroup\$

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

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

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

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


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.

\$\endgroup\$
6
\$\begingroup\$

Factor + koszul, 10 bytes

inversions

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

R, 46 bytes

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

Try it online!

Uses ovs' approach: upvote that!

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

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

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.

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

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!

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

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ Mar 31, 2022 at 21:14
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 25 bytes

Prompts for vector of integers

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

Try it online! Thanks to Dyalog APL Classic

\$\endgroup\$
1
\$\begingroup\$

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

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

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 12 bytes

IΣEθLΦ…θκ›λι

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
  E             Map over values
       θ        Input array
      …         Truncated to length
        κ       Current index
     Φ          Filtered where
          λ     Inner value
         ›      Is greater than
           ι    Outer value
    L           Take the length
 Σ               Take the sum
I                Cast to string
                 Implicitly print
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ -9 \$\endgroup\$
    – att
    Apr 11 at 0:40
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

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