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], 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"
# [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"
# [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"
# [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"
# 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 `+\`
# [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")
# [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"