← Back to context

Comment by ummonk

4 years ago

Why not just use a list comprehension?

  def congruent_sets(m, l):
    return [[v for v in l if v % m == i] for i in range(m)]

4 comments

ummonk

Reply
988747  4 years ago

Isn't that unnecessary quadratic algorithm (nested loops, m*l iterations, instead of m + l)?

  • ummonk  4 years ago

    Yes, but that's the case with all the functional approaches proposed.

    If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).

    • dragonwriter  4 years ago

      > If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).

      itertools.groupby doesn’t return a dictionary, it returns an iterator of (key, (iterator that produces values)) tuples. It sounds, though, like you want something like:

        from itertools import groupby

  def categorize_into_list(source, _range, key):
    first = lambda x: x[0]
    sublist_dict = { 
      k: list(v[1] for v in vs) 
      for k, vs in groupby(sorted(((key(v), v) for v in source), key=first), first))
    }
    return [sublist_dict.get(i, []) for i in _range]

      Then you could do this with something like:

        def congruent_sets(m, l):
    categorize_into_list(l, m, lambda v: v % m)

      1 reply →