Как сформировать все возможности объектов двух измерений

Question

Мне нужно сгенерировать все возможности объектов, помещенных в стеки, вот так:

• Есть n объектов и b стеков
• Мне важно их положение в стеке

Например, если мы заботимся только о том, в каком стеке они находятся, и у нас есть 3 объекта и 2 стека, мы можем создать массив из

(0, 1, 1) - это означает, что объект 1 находится в стеке 0, остальные находятся в стеке 1

Генерация всех комбинаций - это просто (0,0,0) (0,0,1) и т. д.

Если мне действительно нужно знать, что находится над тем, что в стеке, то я не могу знать таким образом

То, о чем я думаю, это также иметь переменную порядка стека, так что для случая (0 , 1, 1), это будет

((0,0), (1,0), (1,1)) или ((0,0), (1,1), (1) , 0)), поэтому первая переменная для каждого находится там, где она есть, а вторая - ее порядок, а 0 - наименьший

Как сгенерировать все возможности в python? (поэтому (0,1,1) будет иметь 2 перестановки и (1,1,1) имеет 6)

Эффективно ли мое представление ((a, b), ...)?

Answer 1

Другое представление может быть проще: рассмотрите ваши разные стеки как области в одном большом стеке, тогда распределение элементов по стекам можно рассматривать как (а) перестановку всех элементов и (б) разбиение эта перестановка в разные стеки. Например, для n=5 и b=3 один такой раздел перестановки может быть [4 3 | 1 | 2 5], то есть первый стек равен [4, 3], второй просто [1], а третий [2, 5].

import itertools

def partitions(lst, minim, num_part):
    if not lst and num_part == 0:
        yield []
    elif lst and num_part > 0:
        for i in range(minim, len(lst) + 1):
            for p in partitions(lst[i:], minim, num_part-1):
                yield [lst[:i]] + p

def distribute(n, b):
    for perm in itertools.permutations(range(n)):
        yield from partitions(perm, 1, b)

for x in distribute(5, 3):
    print(x)

Результаты (некоторые из 720 для n=5 и b=3, по крайней мере, с одним элементом в стеке (minim=1))

[(0,), (1,), (2, 3, 4)]
[(0,), (1, 2), (3, 4)]
....
[(2, 3), (0, 1), (4,)]
...
[(4, 3, 2), (1,), (0,)]

И если вам нужно (stack, position) формат, не должно быть слишком сложно преобразовать результат в этот формат на этапе последующей обработки.

Answer 2

Вы можете сгенерировать комбинации, используя itertools, например:

>>> prod = itertools.product(range(3), range(2), range(5))
>>> [x for x in prod]
[(0, 0, 0), (0, 0, 1), (0, 0, 2), (0, 0, 3), (0, 0, 4), (0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 1, 4), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 0, 3), (1, 0, 4), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 0, 3), (2, 0, 4), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 1, 4)]

В зависимости от чисел это может быть очень неэффективно, но для небольших значений это будет хорошо.