Как создать все возможные способы маркировки (классификации) набора объектов, используя набор меток в Python? - PullRequest
Новая
       11

Как создать все возможные способы маркировки (классификации) набора объектов, используя набор меток в Python?

2 голосов
/ 30 марта 2019

Предположим, что у нас есть набор объектов: 

set_of_objects = {1, 2, 3, 4, 5}

и набор классов: 

set_of_classes = {'a', 'b', 'c'}

Как мы можем сгенерировать все способы классификации набора объектов ввсе возможные классы в наборе классов в python?

Пример вывода будет примерно таким: 

[[1],[2],[3]]
[[1,2],[3],[]]
[[1,2,3],[],[]]
[[3],[2],[1]]
and so on...

Число всех способов, которыми мы можем классифицировать n объектов в k классов:: k ^ n, потому что мы можем назначить каждый из n объектов в k классов.

Ответы [ 2 ]

1 голос
/ 30 марта 2019

Вы можете создать рекурсивный алгоритм для создания раздела: 

import itertools

def part(lst, n):
    if n <= 1:
        # single answer for 1 partition
        yield [lst]
    else:
        for m in range(len(lst)+1):
            for head in itertools.combinations(lst, m):
                nothead = [x for x in lst if x not in head]
                for tail in part(nothead, n-1):
                    yield [list(head)]+tail

def partition(n):
    lst = list(range(n))
    for x in part(lst, n):
        print(x)

Пример: partition(3): 

[[], [], [0, 1, 2]]
[[], [0], [1, 2]]
[[], [1], [0, 2]]
[[], [2], [0, 1]]
[[], [0, 1], [2]]
[[], [0, 2], [1]]
[[], [1, 2], [0]]
[[], [0, 1, 2], []]
[[0], [], [1, 2]]
[[0], [1], [2]]
[[0], [2], [1]]
[[0], [1, 2], []]
[[1], [], [0, 2]]
[[1], [0], [2]]
[[1], [2], [0]]
[[1], [0, 2], []]
[[2], [], [0, 1]]
[[2], [0], [1]]
[[2], [1], [0]]
[[2], [0, 1], []]
[[0, 1], [], [2]]
[[0, 1], [2], []]
[[0, 2], [], [1]]
[[0, 2], [1], []]
[[1, 2], [], [0]]
[[1, 2], [0], []]
[[0, 1, 2], [], []]
0 голосов
/ 30 марта 2019

Я сам нашел решение, но не буду отмечать его как ответившее, чтобы увидеть, существуют ли более эффективные методы для этого.Мое решение: 

set(itertools.product(set_of_classes, repeat=len(set_of_objects))

Фактически это повысит set set_of_classes до (декартовой) степени len (set_of_objects).Есть идеи получше?

...