Count inversions

Code Golf

counting sequence add tag

xnor

Given a list of 0's and 1's, count its number of *inversions*, instances where a 1 precedes a 0, not necessarily immediately before. That is, the number of pairs of indices $i,j$ with $i<j$ but $l_i > l_j$. This tells you how many swaps of two adjacent elements are needed to sort the list.

In place of `1`/`0`, you may instead use `True`/`False` or characters `'1'`/`'0'`. You may not swap the two labels.

### Test cases

| Input                 | Output                 |
|-----------------------|------------------------|
| `[1, 0]`                  | `1`                   |
| `[0, 0, 0, 1, 1, 1]`                  | `0`                   |
| `[1, 1, 0, 1, 0, 1]`                  | `5`                   |
| `[1, 1, 0, 0] `                  | `4`                   |
| `[0]`                  | `0`                   |
| `[]`                  | `0`                   |
| `[1, 0, 1, 1, 0, 0, 0, 1, 1]`                  | `10`                   |

[Rust](https://www.rust-lang.org/), 67 bytes

wizzwizz4

Python 2 [Python](https://docs.python.org/2/), 40 bytes

xnor

Haskell [Haskell](https://www.haskell.org/), 28 bytes

xnor

Python 3 [Python 3](https://docs.python.org/3/), 57 bytes

DJMcMayhem

APL (Dyalog Unicode) Dyalog APL, 6 bytes

Anonymous 976

Clean [Clean](https://clean.cs.ru.nl/Clean), 42 bytes

Οurous

Haskell [Haskell](https://www.haskell.org/), 34 bytes

Anonymous 976

Top Answer

wizzwizz4

# [Rust], 67 bytes

    |a:&[_]|{let mut c=0;let mut t=0;for x in a{if*x{c+=1}else{t+=c}}t}

[Try it online!][TIO-kdbnlvqk]

Each `0` adds the number of preceding `1`s to the total, so this answer keeps a running total of the number of `1`s seen so far (`c`) and adds that to the total (`t`) whenever it sees a `0`.

Ungolfed:

    |a: &[bool]| {
        let mut count = 0;
        let mut total = 0;
        for x in a {
            if *x {
                count += 1
            } else {
                total += c
            }
        }
        total
    }

[Rust]: https://www.rust-lang.org/
[TIO-kdbnlvqk]: https://tio.run/##pVLNjoIwEL73KUYPCqsxkOxecPGwj7CHvRhjurWNZGtxaXFNoM/OtggE/9CEOdB2vp@ZoU1SqQomYIcj4biQITDBqQIGYZHjYLRcr/LMJnapAhJ683qvzJ7FCRwhEoCziL0cMzIJfU25pJmahERrpQvrNy9dsZQ0UWv6O3CYM1qqJKVTYNiwV@4UfPcmq8QrWrOcpPZrlZ7b4d@qcuNg5W9Py5teXzt67ejoYbNX410OfnN@33qWpqmkINUmCKI4CDJJOZvCR8o@Kd7oU1l7YTwS1N6ZJRm2vfcZj8mPXQwkm2dQP4VDAF@UvH/HMV9AWOob3MYsFX8J3jvueZZscSIvkzvDy0lu3psiWyCtSnWMvTGEi2rUa9Qv0fIPXIFrC@2xiMjAcc9hfdlczDklyqmuw8Y@iYTiYuAMMz00/9oZHdwK1kgXfs/wegbyjIdxsU5@vT@dzvNtrIt/T3ePj/pO2HsC9KgienqGuwpUo6ilqU7It@s/ "Rust – Try It Online"

Answer #2 Python 2

xnor

# [Python], 40 bytes

    f=lambda l:l>[]and-~-l.pop()*sum(l)+f(l)

[Try it online!][TIO-k7cmu24j]

[Python]: https://docs.python.org/2/
[TIO-k7cmu24j]: https://tio.run/##K6gsycjPM/r/P802JzE3KSVRIccqxy46NjEvRbdON0evIL9AQ1OruDRXI0dTOw1I/E/LL1LIUcjMU4iONtQxiNVRiDbQAUFDEARxQQwDCEZwIQpBBEQMoh6uMzbWiouzoCgzr0QBbAkA "Python 2 – Try It Online"

Answer #3 Haskell

xnor

# [Haskell], 28 bytes

    f(h:t)=sum[h|0<-t]+f t
    f _=0

[Try it online!][TIO-k79bry0e]

[Haskell]: https://www.haskell.org/
[TIO-k79bry0e]: https://tio.run/##y0gszk7Nyfn/P00jw6pE07a4NDc6o8bARrckVjtNoYQrTSHe1uB/bmJmnoKtQkFRZl6JgopCbmKBQhqQjo421DGI1VGINtABQUMQBHFBDAMIRnAhCkEERAyiHq4zNvb/v@S0nMT04v@6yQUFAA "Haskell – Try It Online"

Answer #4 Python 3

DJMcMayhem

# [Python 3], 57 bytes

```python
lambda l:sum(sum(l[:i+1])*(not e)for i,e in enumerate(l))
```

[Try it online!][TIO-k7ccz0u6]

[Python 3]: https://docs.python.org/3/
[TIO-k7ccz0u6]: https://tio.run/##K6gsycjPM/6fZhvzPycxNyklUSHHqrg0VwOEc6KtMrUNYzW1NPLySxRSNdPyixQydVIVMvMUUvNKc1OLEktSNXI0Nf/nKNgqRBvqKBjoKBiCkQEMgbixXAVFmXklGmlgtQA "Python 3 – Try It Online"

Answer #5 APL (Dyalog Unicode)

Anonymous 976

# Dyalog APL, 6 bytes

```
~+.×+\
```

A train. Decomposes to the dfn `{(~⍵) +.× (+\⍵)}` (`⍵` is the right argument).

`\` is scan, and `+` is addition, so `+\` is scan by addition performing cumulative summation on the argument, the result of which indicates the number of 1s encountered

`~` is complement, each bit of the argument vector is flipped

`+.×` on vectors this performs the dot product between the results of `~` and `+\`

Answer #6 Clean

Οurous

# [Clean](https://clean.cs.ru.nl/Clean), 42 bytes
```clean
import StdEnv
$[h:t]=sum[h\\0<-t]+ $t
$_=0
```
[Try it online!](https://tio.run/##XY4/D4IwEMVn@iluYIAISUl0MbLpYOLGWBrTQBUSWow9NH55a/kjEZPL5d57d7@2aKTQVrVl10hQota2Vrf2jpBhedAP4rNqizw1nWJVntNdjHwFPhL/nFKboXCbKQhdAvOh1rfOyRTaDvspzyEYvGhyQtjFgNKg4eRZybsk3qAcghHPC1gSAeURJGE0SOrkUMlYLqJTNDp07i7a/Ec9av1F/dwuMTN@8Vr/Cxq6HW7fxaURV2Pj48nuX1qoujAf "Clean – Try It Online")

Answer #7 Haskell

Anonymous 976

# [Haskell], 34 bytes

    f=(0%)
    a%(q:w)=(a+q)%w+a-a*q
    _%_=0

[Try it online!][TIO-k77wjzkw]

[Haskell]: https://www.haskell.org/
[TIO-k77wjzkw]: https://tio.run/##y0gszk7Nyfn/P81Ww0BVkytRVaPQqlzTViNRu1BTtVw7UTdRq5ArXjXe1uB/bmJmnm1BUWZeiUpatIGOAhAZwkgIAy5oGPsfAA "Haskell – Try It Online"

7 Answers