Как найти все разбиения списка S на k подмножеств (может быть пустым)? - PullRequest
Новая
       11

Как найти все разбиения списка S на k подмножеств (может быть пустым)?

0 голосов
/ 27 декабря 2018

У меня есть список уникальных элементов, скажем, [1,2], и я хочу разделить его на k = 2 подсписков.Теперь я хочу иметь все возможные подсписки: 

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

И я хочу разделить на 1 <= k <= n подсписков, поэтому для k = 1 это будет: </p> 

[ [1, 2] ]

Как я могу сделать это с Python 3?

ОБНОВЛЕНИЕ: моя цель состоит в том, чтобы получить все возможные разделы списка из N уникальных номеров, где каждый раздел будет иметь k подсписков.Я хотел бы показать лучший пример, чем я показал выше, я надеюсь, что я не пропущу что-тоПоэтому для списка [1, 2, 3] и для k = 2 я хочу иметь следующий список: 

[
[ [1,2,3], [] ],
[ [2,3], [1] ],
[ [1,3], [2] ],
[ [1,2], [3] ],
[ [1], [2,3] ],
[ [2], [1,3] ],
[ [3], [2,3] ],
[ [], [1,2,3] ]
]

ОБНОВЛЕНИЕ 2: до сих пор я объединил два предложения, и небольшая модификация получила следующий код: 

def sorted_k_partitions(seq, k):
    """Returns a list of all unique k-partitions of `seq`.

    Each partition is a list of parts, and each part is a tuple.

    The parts in each individual partition will be sorted in shortlex
    order (i.e., by length first, then lexicographically).

    The overall list of partitions will then be sorted by the length
    of their first part, the length of their second part, ...,
    the length of their last part, and then lexicographically.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

С помощью этой функции я могу сделать следующее: 

import itertools as it
k=2
S = [1, 2, 3]
for i in (range(k)):
    for groups in sorted_k_partitions(S, k-i):
        for perm in it.permutations(groups+[tuple() for j in range(i)]):
            print(perm)

Вывод: 

((1,), (2, 3))
((2, 3), (1,))
((2,), (1, 3))
((1, 3), (2,))
((3,), (1, 2))
((1, 2), (3,))
((1, 2, 3), ())
((), (1, 2, 3))

Я еще не уверен, что этот код дает мне праворешение, может быть, есть другой способ?

1 Ответ

0 голосов
/ 27 декабря 2018

Вот альтернативное решение: 

def partition_k(l, k):
    n = len(l)
    if k > n:
        raise ValueError("k = {0} should be no more than n = {1}".format(k, n))

    if n == 0:
        yield []
        return

    pos = [0] * n
    while True:
        # generate output for the value
        out = [[] for _ in range(k)]
        for i in range(n):
            out[pos[i]].append(l[i])
        yield out

        #increment the value
        pos[0] += 1
        for i in range(n):
            # should we carry from this digit to the next one?
            if pos[i] == k:
                # overflow of the whole value?
                if i == n - 1:
                    return
                pos[i] = 0
                pos[i + 1] += 1
            else:
                break

Пусть n - длина списка, а k - количество разделов.Идея этого кода заключается в том, что каждая строка вывода может быть представлена ​​как число n цифр в системе base- k.Каждая «цифра» показывает, в каком сегменте идет значение в соответствующей позиции.Например, строка 

[[2,3], [1], [4]]

может быть закодирована как [1,0,0,2], что означает, что

  • 1 идет в корзину # 1
  • 2 идет введро # 0
  • 3 идет в ведро # 0
  • 4 идет в ведро # 2

Очевидно, что каждый такой n -цифра base- k число представляет действительный раздел списка, и каждый раздел представлен некоторым числом.Таким образом, чтобы сгенерировать все разделы, нам нужно просто перебрать все такие числа и сгенерировать соответствующие разделы.Это легче сделать, если вы используете список цифр для представления числа (в коде это pos).

...