Comment by 988747

4 years ago

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

3 comments

988747

Reply
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)