1-liner + imports: O(n²) but faster than with "for" clear solution for Count Inversions by Phil15 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

1-liner + imports: O(n²) but faster than with "for" solution in Clear category for Count Inversions by Phil15

from itertools import combinations, starmap
from operator import gt

def count_inversion(seq): return sum(starmap(gt, combinations(seq, 2)))

Nov. 4, 2020

Comments:

ddavidse on Jan. 20, 2021, 9:08 a.m.
I have no idea what's going on here but that's the shortest solution I've seen. I guess I'll have to look up what "starmap" and "gt" do

Phil15 on Jan. 20, 2021, 9:56 a.m.
Equivalent to `sum(x > y for x, y in combinations(seq, 2))` `gt` stands for greater than (`>`). Objects (like int) can have `gt` magic method that stand for that too. Same for lower than `lt <`, lower or equal `le <=`, equal `eq ==`, not equal `ne !=`, greater or equal `ge >=`. About starmap, it is similar to `map` with a star `*`. We clearly use it less often but it's quite nice too. <pre class='brush: python'>list(map(f, [a, b, c])) == [f(a), f(b), f(c)] list(starmap(f, [a, b, c])) == [f(*a), f(*b), f(*c)] </pre> So <pre class='brush: python'>sum(starmap(gt, combinations(seq, 2))) sum(gt(*args) for args in combinations(seq, 2)) sum(gt(x, y) for x, y in combinations(seq, 2)) sum(x > y for x, y in combinations(seq, 2)) </pre> But why is it faster than a for loop? I don't have a deep deep understanding of it but map and starmap handles the "for loop" with `C` code. And `gt` probably written in `C` too. While a "for" loop is written in python. So it's faster.

List, list and list again

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.