У меня есть следующий рекурсивный генератор, который выдает каждую комбинацию чисел от 0 до 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
  

Если вызывается как f(3, 3) это, выдает значения

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

(Попробуйте вызвать его как list(f(3,3)) , чтобы получить их в виде списка.)

Мне нужно получить одни и те же значения в другом порядке: я хочу, чтобы значения были отсортированы по их максимуму, т. Е. Сначала значение [0, 0, 0] , затем все значения, которые имеют 1 значение maximum , т. Е. [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], ... Затем те, которые содержат a 2 , т. е. [0, 0, 2], [0, 1, 2], [0, 2, 0], [0, 2, 1], [0, 2, 2], [2, 0, 0], ... и т. Д.

Генератор никогда не должен выдавать значения дважды (конечно), и должна быть возможность вызывать его с очень большими значениями, такими как 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
  

Есть идеи?

 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 и ее результата добавляются операторы Print.
Комментарий к h функции должен быть достаточно ясным, чтобы объяснить общую идею.

Я сам нашел решение. Сначала я перебираю верхнее значение, затем генерирую все значения, которые имеют одно или несколько из этого верхнего значения. Для этого я перебираю количество верхних значений (от 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) ]
  

Но я все же хотел бы пригласить вас предложить более элегантные решения. Мне это все еще кажется методом грубой силы, и способ, которым я создаю значения, которые я получаю, конечно, не самый дешевый, который я когда-либо видел.

Идея растущего куба

(обновлено из «диагональной» идеи)

Когда я рисую задачу на бумаге, я пришел к чему-то вроде:

  |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 ..), Поэтому их конечное число.

Если вы найдете правило для сканирования всех координат на этой растущей поверхности куба, вы получите запрошенный вами генератор.

Я совершенно уверен, что ваша функция f выдает те же значения, itertools.product что и; ie. Я думаю, вы можете заменить 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
  

Вот алгоритм для генерации следующей лексикографической перестановки (кстати, мне также нравится идея каждого набора в виде чисел с разным основанием; например, основание 1 основание 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]
  

Сначала обратите внимание, что вы можете легко сгенерировать список уникальных решений, содержащих 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]]