(-items.count(x), items.index(x)) clear solution for Sort Array by Element Frequency by flpo - python coding challenges

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

(-items.count(x), items.index(x)) solution in Clear category for Sort Array by Element Frequency by flpo

def frequency_sort(items):
    return sorted(items, key=lambda x: (-items.count(x), items.index(x)))

Dec. 7, 2018

Comments:

oduvan on Dec. 10, 2018, 5:26 p.m.
bellisimi

Denis_Gerashchenko on Feb. 12, 2019, 5:15 p.m.
I wonder how does this sorting works? How does it possible to sort a list with a key - lambda expression that returns a tuple for each element?

martin.pilka on Feb. 13, 2019, 3:48 p.m.
Exactly, labmda returning tuple for each element.

Denis_Gerashchenko on Feb. 13, 2019, 5:07 p.m.
I have got it, but how actually this sorting method works? With a tuple as a key. As I know, the function provided in key argument is aplied to each element of the sequence, and then function sorts it acending or else, but... I don't understant how this is possible: 1. Input - frequency_sort([4, 6, 2, 2, 6, 4, 4, 4]) 2. After applying the key: (-4, 0), (-2, 1), (-2, 2), (-2, 3), (-2, 4), (-4, 5), (-4, 6), (-4, 7) 3. Output: [4, 4, 4, 4, 6, 6, 2, 2]

NexTg.Loki on Feb. 14, 2019, 1:53 p.m.
I recommended read a bit more about tuple <a href="https://docs.python.org/3/reference/expressions.html#comparisons">comparison</a>. Tuples compare lexicographically using comparison of corresponding elements, whereby reflexivity of the elements is enforced. That is when first value of tuple is equal to another first value of tuple a compare method will use next value. For example: <pre class='brush: python'>(-3, 2) < (-4, 3) #False, becouse -3 > -4 (-4, 2) < (-4, 3) #True, becouse -4 == -4 and 2 < 3 </pre>

Denis_Gerashchenko on Feb. 14, 2019, 1:58 p.m.
Thank, now it's clear for me

BeginBye on March 6, 2019, 3:12 p.m.
NexTg.Loki, could you please go a bit more deeply with your explanation of how it works. I long to figure out the logic, how sorted() uses the tuples here for sorting. Ok, we have here a two-element tuple for each element in the array given, where first element stands for frequency, and the second one - for its index in the array. What is going on next? Why must one of the elements be negative? Could you please give more detailed explanation, or to just point out on a resource to read of it more? I do like your solution!

jadeunimelb on June 5, 2019, 10:55 p.m.
I'm sure you figured this one out already by now, but if not; - When python sorts tuples of (x, y, z) it will sort by x - For a tie in x in will sort by y, and so on. By using a tuple as the key, you are saying: "For this item: 6, read it as this: {(4,1): 6}". You do this for each item, and when you sort, you sort the items by the tuples you have created as the keys.

jiachxxj on April 12, 2019, 4:19 p.m.
After applying the key ,the result should be: (-4,0),(-2,1),(-2,2),(-2,2),(-2,1),(-4,0),(-4,0),(-4,0)

Christopher_Bouma on Feb. 7, 2020, 12:28 a.m.
Thanks this helped. I was trying to follow along with the key result that was posted above, and wasn't understanding how the second '6' would be sorted in front of the '2's. After applying the key: (-4, 0), (-2, 1), (-2, 2), (-2, 3), (-2, 4), (-4, 5), (-4, 6), (-4, 7) But it is because when it calls index('6') it returns the value of the first instance.

xiad2009 on Nov. 24, 2021, 3:03 p.m.
index function return the first index of the item appeared in the list, so index(6)==1, index(2)==2 and index(4)==0. That means after applying, it will be:(-4,0),(-2,1),(-2,2),(-2,2),(-2,1),(-4,0),(-4,0),(-4,0), but not(-4, 0), (-2, 1), (-2, 2), (-2, 3), (-2, 4), (-4, 5), (-4, 6), (-4, 7). So it can sort 6 cause (-2,1) <(-2,2)

vlad.bezden on Feb. 17, 2019, 12:48 a.m.
Very interesting and clever solution. However, keep in mind this solution is about 15 times slower than using collections.Counter solution <a href="https://py.checkio.org/mission/sort-array-by-element-frequency/publications/vlad.bezden/python-3/first/">https://py.checkio.org/mission/sort-array-by-element-frequency/publications/vlad.bezden/python-3/first/</a> I ran test: <pre class='brush: python'>for f in [frequency_sort_fast, frequency_sort_slow]: t = timeit(stmt="f(items)", number=100, globals=globals()) print(f"{f.__name__} took: {t:.6f}") </pre> and I got 0.18 seconds for using counter and 2.8 seconds for using this solution

kim.yangjin on Aug. 8, 2020, 5:02 p.m.
Hi, vlad, How would be the speed if it doesn't use tuple? def frequency_sort(items): return sorted(items, key=lambda x: -items.count(x)+items.index(x)*0.1)

seed5 on April 7, 2021, 3:52 a.m.
hey, Vlad, I tested number=100000 and the flpo's solution runs slightly faster on my computer (and that's even considering that you don't timeit the import of collection libraries): frequencysort : 0.23105010300059803 frequencysort_coll: 0.33440620299370494 <pre class='brush: python'>from typing import List, Any, Iterator, Union from collections import Counter import timeit data = [4, 6, 2, 2, 6, 4, 4, 4] # data = ['bob', 'bob', 'carl', 'alex', 'bob'] InputData = List[Any] OutputData = Union[InputData, Iterator[Any]] def frequency_sort(items): result = sorted(items, key=lambda x: (-items.count(x), items.index(x))) return result def frequency_sort_collections(items: InputData) -> OutputData: c = Counter(items) result = sorted(c.elements(), key=lambda k: c[k], reverse=True) return result if __name__ == '__main__': x = timeit.timeit("frequency_sort_best(data)", number=100000, setup="from __main__ import frequency_sort_best, data") y = timeit.timeit("frequency_sort_collections(data)", number=100000, setup="from __main__ import frequency_sort_collections, data") print(f"frequency_sort : {x}") print(f"frequency_sort_coll: {y}") # output: frequency_sort : 0.23105010300059803 frequency_sort_coll: 0.33440620299370494 </pre>

CedricVaruna on Nov. 27, 2022, 2 a.m.
Weird, I get different results on my computer, I share the script I used to measure that for what it's worth: <pre class='brush: python'>from timeit import timeit from typing import Iterable from operator import indexOf def frequency_sort(items: list[str | int]) -> Iterable[str | int]: return sorted( items, key=lambda i: items.count(i) * len(items) - indexOf(items, i), reverse=True, ) def frequency_sort_slow(items): return sorted(items, key=lambda x: (-items.count(x), items.index(x))) from collections import Counter def frequency_sort_fast(items): groups = Counter(items) sort = sorted(groups.items(), key=lambda e: e[1], reverse=True) for key, value in sort: yield from [key]*value items = [4, 6, 2, 2, 6, 4, 4, 4] for f in [frequency_sort_fast, frequency_sort_slow, frequency_sort]: t = timeit(stmt="f(items)", number=1000, globals=globals()) print(f"{f.__name__} took: {t:.6f}") #Output: #frequency_sort_fast took: 0.000201 #frequency_sort_slow took: 0.003222 #frequency_sort took: 0.003396 </pre>

serg3y1999 on March 24, 2019, 3:23 p.m.
can u explain why do u use minus before "-items.count(x)" ?

serg3y1999 on March 31, 2019, 9:17 a.m.
ooh,ok ,i got it,cause we need deacreasing order, thx

martin.pilka on April 12, 2019, 6:37 p.m.
Yes, you're right, we need decreasing order.

PHANTOM0308 on May 2, 2019, 2 a.m.
This is f.king awesome 0.0

Fatii on June 9, 2019, 12:12 p.m.
Lets try putting list of 1000000 entries in items, not even close to being efficient. Timed it on my personal laptop and for 30_000 items got 32,43s, for hobby usage it's ok but get industrial load of data and you just killed everything :D

flpo on June 9, 2019, 12:46 p.m.
I would say this is somehow obvious... Indeed, this solution is in "clear" category and not in "speedy" :-) What is nice about this solution is exactly his clearness, since IMO it is basically the Python translation of the sentence: "sort the items by their frequency and their original position in case of same frequency", isn't it?

ibalashov852 on July 9, 2019, 12:38 p.m.
This is N^2 complexity, but it's pretty!

gvswamy on Sept. 6, 2019, 7:17 a.m.
Intelligent, but high run time complexity because of count() on each element. My solution using Counter and comprehension is, return [k for k,v in Counter(items).most_common() for i in range(v)])

flpo on Sept. 6, 2019, 9:04 a.m.
Sure, this solution is clearly not efficient, but it is clear :) BTW, <a href="https://py.checkio.org/mission/sort-array-by-element-frequency/publications/flpo/python-3/with-itertools-batteries-chain-repeat-starmap/">you can also use a few batteries</a> from `itertools` :P

open4mail on Sept. 12, 2019, 11:34 a.m.
Nice and clear sollution. but it's sad that effective sollutions and clear sollutions rarely the same.

hangezhaoyh on Sept. 25, 2019, 6:34 a.m.
items.sort(reverse=True, key=lambda x: (-items.count(x), items.index(x))) this is not right, why?

koborC on Nov. 17, 2020, 2:56 p.m.
if you use "reverse = True" then use items.count(x) instead of - items.count(x). Also items.sort() will affect outside of the function: eg. <pre class='brush: python'>def some_function(l : list) -> list: l.sort() return l = [2,2,3,1] some_function(l) print(l) # ->[1,2,2,3] </pre>

r.rothkugel on Oct. 4, 2019, 10:25 a.m.
Clever, but slow. Can't Recommend.

piter239 on March 16, 2020, 4:45 p.m.
I love this solution for the clarity of it!

Patrick_Devaney on April 2, 2020, 12:06 a.m.
taught me about comparing tuples, neat!

piter239 on April 18, 2020, 9:32 a.m.
Exactly!

five_east_west on April 19, 2020, 12:41 p.m.
1.Input - frequency_sort([4, 6, 2, 2, 6, 4, 4, 4]) 2.After applying the key: (-4, 0), (-2, 1), (-2, 2), (-2, 3), (-2, 4), (-4, 5), (-4, 6), (-4, 7) 3.Output: [4, 4, 4, 4, 6, 6, 2, 2] I am not understand why the second '6' will appear bofore the first,according to the compare with the tuple,the first '2' is(-2,1),the second '6' is (-2,4).The second element in the tuple the '6' is bigger than '2',so in my opinoin the sorted list shuold be [4, 4, 4, 4, 6, 2, 2, 6].

wally.liangsi on May 17, 2021, 8:01 a.m.
After applying the key ,the result should be: (-4,0),(-2,1),(-2,2),(-2,2),(-2,1),(-4,0),(-4,0),(-4,0) index return the first occurrence of x in the array Just for your reference.

AndriiDiachenko on May 1, 2020, 3:29 p.m.
Wow

helebed on Oct. 7, 2020, 8:09 p.m.
Wow!, I have a lot to learn to code like this... Thank you!

Poiu on Dec. 16, 2020, 12:38 a.m.
I've just resolved this exercise with loops, variables accumulating values... Lots of lines for just doing the same as you (and you're using methods that I already know). Reading other's solutions is a great tool to improve coding.

IliaLiash on Jan. 13, 2021, 7:29 p.m.
Boss

natter1 on April 4, 2021, 12:31 p.m.
Is it really ok to assume, that every iterable (thats what was stated as input in the task) has an index() method? What about e.g. a set as input?

tkachuk.constantine on May 7, 2021, 12:52 a.m.
Cool! Thanks for sharing! I learn new for me in comparison.

libeadier on July 16, 2021, 6:28 p.m.
Great!

pyrexdraum on July 25, 2021, 7:37 a.m.
Genius!

H0r4c3 on Jan. 31, 2023, 6:19 p.m.
Great idea the use of lambda function!

List, list and list again

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!