Все кортежи натуральных чисел

Question

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

(1, 1, 1)
(2, 1, 1)
(1, 2, 1)
(1, 1, 2)
(2, 2, 1)
(2, 1, 2)
(2, 2, 2)
(3, 2, 2)
(2, 3, 2)
# and so on...

Answer 1

Вы можете сгенерировать все наборы натуральных чисел, перечислив их на основе их итогов (итого = 3 первых, итого = 4 секунды, итого = 5 третьих и т. Д.).Обратите внимание, что total = 3 - это наименьшее возможное значение, так как каждый элемент является положительным, поэтому мы начинаем с t=3.

. Внутри каждого итога этот код генерирует их в лексикографическом порядке.

def posint():
    t = 3
    while True:
        for i in range(1, t-1):
            for j in range(1, t-i):
                    yield i, j, t-i-j
        t += 1

for i, j, k in posint():
    print(i, j, k)

Если вам нужна более общая версия, которая принимает параметр n, описывающий длину кортежей, вы можете перечислить кортежи с суммой t, используя "Звезды и полосы" .Это дает вам неотрицательные кортежи, но вы можете добавить один к каждому значению, чтобы получить уникальные положительные кортежи.

import itertools

def posint(n):
    for t in itertools.count(0):
        for c in itertools.combinations(range(t + n - 1), n - 1):
            yield [c[0]+1] + [c[i]-c[i-1] for i in range(1, len(c))] + [t+n-1-c[-1]]

for c in posint(5):
    print(c)

Более простой для понимания общий метод перечисляет комбинации на основе их наибольшего значения ипервый столбец, в котором отображается значение. В этой схеме результат с наибольшим значением t и значением t, отображаемым в i-м столбце, имеет произвольные значения меньше t в столбцах слева от i и произвольные значения меньше или равныв столбцах справа от i.

Этот метод относительно прост для понимания, но порядок, в котором получаются результаты, немного странен.

import itertools

def posint(n):
    for t in itertools.count(1):
        for i in range(n):
            for c1 in itertools.product(range(1, t), repeat=i):
                for c2 in itertools.product(range(1, t+1), repeat=n-i-1):
                    yield c1 + (t,) + c2

for c in posint(3):
    print(c)

Answer 2

Этот код использует подход, аналогичный подходу Пола Ханкина, но он более общий, поскольку он будет генерировать кортежи любой желаемой ширины, а не только 3.

from itertools import combinations, count

def compositions(num, width):
    m = num - 1
    first, last = (-1,), (m,)
    for t in combinations(range(m), width - 1):
        yield tuple(v - u for u, v in zip(first + t, t + last))

def ordered_compositions(width):
    for n in count(width):
        yield from compositions(n, width)

# test

width = 3
for i, t in enumerate(ordered_compositions(width), 1):
    print(i, t)
    if i > 30:
        break

output

1 (1, 1, 1)
2 (1, 1, 2)
3 (1, 2, 1)
4 (2, 1, 1)
5 (1, 1, 3)
6 (1, 2, 2)
7 (1, 3, 1)
8 (2, 1, 2)
9 (2, 2, 1)
10 (3, 1, 1)
11 (1, 1, 4)
12 (1, 2, 3)
13 (1, 3, 2)
14 (1, 4, 1)
15 (2, 1, 3)
16 (2, 2, 2)
17 (2, 3, 1)
18 (3, 1, 2)
19 (3, 2, 1)
20 (4, 1, 1)
21 (1, 1, 5)
22 (1, 2, 4)
23 (1, 3, 3)
24 (1, 4, 2)
25 (1, 5, 1)
26 (2, 1, 4)
27 (2, 2, 3)
28 (2, 3, 2)
29 (2, 4, 1)
30 (3, 1, 3)
31 (3, 2, 2)

---

Алгоритм для compositions был получен из методики, используемой для подсчета количества композиций, объясненных в статье Википедии о составах .По сути, это вариация хорошо известной техники Звезды и бары .

Answer 3

Это метод грубой силы, который не требует упорядочения.

Предупреждение : Использование set через toolz.unique, как здесь, для удаления дубликатов, требует много памяти и дорого.Есть лучшие способы.

from itertools import count, product, chain
from toolz import unique

def gen_tups(n):
    yield from unique(chain.from_iterable(product(range(1, c), repeat=n) \
                      for c in count(start=2))):

x = gen_tups(3)

next(x)  # (1, 1, 1)
next(x)  # (1, 1, 2)
next(x)  # (1, 2, 1)

Примечание toolz.unique реализует этот широко используемый рецепт , поэтому вам не нужен доступ к сторонней библиотеке.