Generator for special combinations

Question

I have the following recursive generator that gives each combination of numbers from 0to 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), it gives 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 to name it as list(f(3,3))to get them as a list.)

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

(), , f(4, 1000), ( , ).

, , f(w, 0), f(w, 1), f(w, 2) , , , :

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

?

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

:

=== 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]

, h . h , .

Answer 2

. , , . ( 1 ). , . .

, :

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

. - , , , , , , .

Answer 3

( "" )

, - :

 |0|1|2|3|
-|-|-|-|-|
0|a|b|c|d|
-|-|-|-|-|
1|b|b|c|d|
-|-|-|-|-|
2|c|c|c|d|
-|-|-|-|-|
3|d|d|d|d|
-|-|-|-|-|

2-D, , .

a, b, c, d , .

, n- .

( ). , (0, 1, 2..), .

, , .

Answer 4

, f , itertools.product; . , f :

from itertools import product

def f(width, top):
    for p in product(range(top), repeat=width):
        yield list(p)

, , itertools.groupby:

from itertools import groupby
from collections import defaultdict

def group_by_max_value(x, y):
    grouped = defaultdict(list)
    for k, g in groupby(f(x, y), key=max):
        grouped[k].extend(list(g))
    return [grouped[k] for k in sorted(grouped.keys())]

, .

from itertools import groupby
from collections import defaultdict

def lazy_group_by_max_value(width, top):
    grouped = defaultdict(list)
    # using `itertools.product` with a `range` object
    # guarantees that the product-tuples are emitted
    # in sorted order.
    ps = product(range(top), repeat=width)
    for k, g in groupby(ps, key=max):
        xs = list(g)
        grouped[k].extend(xs)
        # if xs[-1] is of the form (0, 0, .., 0), (1, 1, .., 1), .., (n, n, .., n) etc
        # then we have found all the maxes for `k`, because all future
        # sequences will contain at least one value which is greater than k.
        if set(xs[-1]) == {k}:
            # `pop` (ie. remove) the values from `grouped`
            # which are associated with key `k`.
            all_maxes_for_k = grouped.pop(k)
            for coll in all_maxes_for_k:
                yield coll

Answer 5

(, , 2 ..):

              :                                                ,         ; , .

Python:

def nextP(perm,top):
  if all (i == top for i in perm):
    return None

  left_max = perm.index(top)

  if all (i == top for i in perm[left_max:]):
    perm[left_max - 1] = perm[left_max - 1] + 1
    perm[left_max:] = [0] * (len(perm) - left_max - 1) + ([0] if perm[left_max - 1] == top else [top])
  else:
    right_max = len(perm) - next(x[0] for x in enumerate(perm[left_max + 1:][::-1]) if x[1] < top) - 1
    perm = perm[:right_max] + [perm[right_max] + 1] + [0] * (len(perm) - right_max - 1)

  return perm

:

permutation = [0,0,2]

while permutation:
  print permutation
  permutation = nextP(permutation,2)

[0, 0, 2]
[0, 1, 2]
[0, 2, 0]
[0, 2, 1]
[0, 2, 2]
[1, 0, 2]
[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]

Answer 6

, , 2, , , 1 . 1. , [1,0,1] [2,0,1], [1,0,2] [2,0,2]. :

import itertools

def g(n) :
    if n == 0 :
        yield [ 0,0,0 ]
    else :
        for x in g(n-1) : # for each solution containing `1` as the maximum
            idx = [ i for (i,xi) in enumerate(x) if xi == n-1 ] # locate the '1' to be incremented
            for j in xrange(1,len(idx)+1) : # increment one '1', then two '1', then three '1', etc
                for tup in itertools.combinations( idx, j ) : # all possible combinations of j '1'
                    y = list(x)
                    for t in tup : # prepare the new solution
                        y[t] += 1
                    yield y

:

list( g(0) )

[[0, 0, 0]]

list( g(1) )

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

list( g(2) )

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