Generator for combinations in special order

Question

I've got the following recursive generator which yields each combination of numbers from 0 to top-1:

def f(width, top):
  if width == 0:
    yield []
  else:
    for v in range(top):
      for subResult in f(width - 1, top):
        yield [ v ] + subResult

If called as f(3, 3) this yields the values

[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], [0, 1, 1], [0, 1, 2],
[0, 2, 0], [0, 2, 1], [0, 2, 2], [1, 0, 0], [1, 0, 1], [1, 0, 2],
[1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 2, 0], [1, 2, 1], [1, 2, 2],
[2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 1, 0], [2, 1, 1], [2, 1, 2],
[2, 2, 0], [2, 2, 1], [2, 2, 2]

(Try calling it as list(f(3,3)) to get these as a list.)

What I need to get is the same values in a different order: I want the values sorted by their maximum, i. e. first the value [0, 0, 0], then all values which have 1 as a maximum, i. e. [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], ..., then those which contain a 2, i. e. [0, 0, 2], [0, 1, 2], [0, 2, 0], [0, 2, 1], [0, 2, 2], [2, 0, 0], ... etc.

The generator shall yield values never twice (of course) and it must be possible to call it with very large values like f(4, 1000) and then simply not drain it completely (so generating all values first and then sorting them after their maximum is out of the question).

The only approach I can think if is first generate all values for f(w, 0), then for f(w, 1), then for f(w, 2) and always skip the values which have been yielded before, but I have the nagging feeling that their might be a better approach:

def g(width, top):
  for t in range(top):
    for v in f(width, t+1):
      if t in v:
        yield v

Any ideas?

Answer 1

def h(width,top,top_count):
    """
    Producing lists of length 'width' containing numbers from 0 to top-1.
    Where top-1 only occur exactly top_count times.
    """
    if width == 0:
        yield []
    elif width == top_count:
        yield [top-1]*top_count
    else:
        for x in range(top-1):
            for result in h(width-1,top,top_count):
                yield [x]+result
        if top_count > 0:
            for result in h(width-1,top,top_count-1):
                yield [top-1]+result


def m(width,top):
    yield [0]*width
    for current_top in range(2,top+1):
        for top_count in range(1,width+1):
            print "=== h{}".format((width,current_top,top_count))
            for result in h(width,current_top,top_count):
                print result
                yield result

ans = [x for x in m(3,3)]

result:

=== h(3, 2, 1)
[0, 0, 1]
[0, 1, 0]
[1, 0, 0]
=== h(3, 2, 2)
[0, 1, 1]
[1, 0, 1]
[1, 1, 0]
=== h(3, 2, 3)
[1, 1, 1]
=== h(3, 3, 1)
[0, 0, 2]
[0, 1, 2]
[0, 2, 0]
[0, 2, 1]
[1, 0, 2]
[1, 1, 2]
[1, 2, 0]
[1, 2, 1]
[2, 0, 0]
[2, 0, 1]
[2, 1, 0]
[2, 1, 1]
=== h(3, 3, 2)
[0, 2, 2]
[1, 2, 2]
[2, 0, 2]
[2, 1, 2]
[2, 2, 0]
[2, 2, 1]
=== h(3, 3, 3)
[2, 2, 2]

Print statements are added to show each call to function h and its result. The comment on h function should be clear enough to explain the general idea.

Answer 2

I found a solution myself. I first loop over the top value, then I generate all values which have one or more of this top value. For that I loop over the amount of top values (1 through width). For each such amount I loop over all positions combinations these top values can have. Then I fill these positions with the top value and the remaining values with a plain product of all values below the top value.

As code, this looks like this:

from itertools import product, combinations

def h(width, top):
  for t in range(top):
    for topAmount in range(1, width+1):  # how many top values are present?
      for topPositions in combinations(range(width), topAmount):
        for fillers in product(
            *[ range(t) for x in range(width-len(topPositions)) ]):
          fillers = list(fillers)
          yield [ t if i in topPositions else fillers.pop()
              for i in range(width) ]

But I still would like to invite you to propose more elegant solutions. This still seems to me like a brute force method, and the way I'm building the values I yield certainly isn't the cheapest I've seen yet.