Hướng dẫn how do you get all the subsets of a list in python? - làm thế nào để bạn có được tất cả các tập hợp con của một danh sách trong python?

Tôi đã không bắt gặp chức năng more_itertools.powerset và sẽ khuyên bạn nên sử dụng nó. Tôi cũng khuyên bạn không sử dụng thứ tự mặc định của đầu ra từ

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

0, thường thay vào đó, bạn muốn giảm thiểu khoảng cách giữa các vị trí và sắp xếp các tập hợp con của các mục có khoảng cách ngắn hơn giữa chúng ở trên/trước các mục có khoảng cách lớn hơn giữa chúng.

Trang công thức

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

1 cho thấy nó sử dụng

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

2

• Lưu ý rằng

  12 ⇒ 1
  13 ⇒ 2
  14 ⇒ 3
  23 ⇒ 1
  24 ⇒ 2
  34 ⇒ 1
  

  3 ở đây phù hợp với ký hiệu tiêu chuẩn cho phần dưới của hệ số nhị thức,

  12 ⇒ 1
  13 ⇒ 2
  14 ⇒ 3
  23 ⇒ 1
  24 ⇒ 2
  34 ⇒ 1
  

  4 thường được gọi là

  12 ⇒ 1
  13 ⇒ 2
  14 ⇒ 3
  23 ⇒ 1
  24 ⇒ 2
  34 ⇒ 1
  

  5 trong các văn bản toán học và trên máy tính (N N Chọn R,)

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Các ví dụ khác ở đây cung cấp sức mạnh của

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

6 theo cách sao cho các bộ đồ 2 được liệt kê theo thứ tự "từ vựng" (khi chúng ta in các số dưới dạng số nguyên). Nếu tôi viết khoảng cách giữa các số cùng với nó (tức là sự khác biệt), nó sẽ hiển thị quan điểm của tôi:

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

Thứ tự chính xác cho các tập hợp con phải là thứ tự 'xả' khoảng cách tối thiểu trước tiên, như vậy:

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

Sử dụng các số ở đây làm cho việc đặt hàng này trông 'sai', nhưng hãy xem xét ví dụ các chữ cái

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

7 rõ ràng hơn tại sao điều này có thể hữu ích để có được quyền hạn theo thứ tự này:

ab ⇒ 1
bc ⇒ 1
cd ⇒ 1
ac ⇒ 2
bd ⇒ 2
ad ⇒ 3

Hiệu ứng này rõ rệt hơn với nhiều mục hơn và với mục đích của tôi, nó tạo ra sự khác biệt giữa việc có thể mô tả các phạm vi của các chỉ mục của Powerset một cách có ý nghĩa.

.

Tôi thực sự chỉ đã viết một chương trình khá liên quan sử dụng mã phân vùng số nguyên nhanh này để xuất các giá trị theo thứ tự thích hợp, nhưng sau đó tôi phát hiện ra more_itertools.powerset và đối với hầu hết sử dụng có lẽ chỉ cần sử dụng chức năng đó như vậy:

from more_itertools import powerset
from numpy import ediff1d

def ps_sorter(tup):
    l = len(tup)
    d = ediff1d(tup).tolist()
    return l, d

ps = powerset([1,2,3,4])

ps = sorted(ps, key=ps_sorter)

for x in ps:
    print(x)

⇣

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

Tôi đã viết thêm một số mã liên quan sẽ in Powerset một cách độc đáo (xem repo cho các chức năng in đẹp mà tôi không bao gồm ở đây:

12 ⇒ 1
13 ⇒ 2
14 ⇒ 3
23 ⇒ 1
24 ⇒ 2
34 ⇒ 1

9,

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

0 và

12 ⇒ 1
23 ⇒ 1
34 ⇒ 1
13 ⇒ 2
24 ⇒ 2
14 ⇒ 3

1).

• REPO: Đơn đặt hàng-Powerset, cụ thể là

  12 ⇒ 1
  23 ⇒ 1
  34 ⇒ 1
  13 ⇒ 2
  24 ⇒ 2
  14 ⇒ 3
  

  2

Điều này khá đơn giản, nhưng vẫn có thể hữu ích nếu bạn muốn một số mã sẽ cho phép bạn đi thẳng vào việc truy cập các cấp độ khác nhau của Powerset:

from itertools import permutations as permute
from numpy import cumsum

# http://jeromekelleher.net/generating-integer-partitions.html
# via
# https://stackoverflow.com/questions/10035752/elegant-python-code-for-integer-partitioning#comment25080713_10036764

def asc_int_partitions(n):
    a = [0 for i in range(n + 1)]
    k = 1
    y = n - 1
    while k != 0:
        x = a[k - 1] + 1
        k -= 1
        while 2 * x <= y:
            a[k] = x
            y -= x
            k += 1
        l = k + 1
        while x <= y:
            a[k] = x
            a[l] = y
            yield tuple(a[:k + 2])
            x += 1
            y -= 1
        a[k] = x + y
        y = x + y - 1
        yield tuple(a[:k + 1])

# https://stackoverflow.com/a/6285330/2668831
def uniquely_permute(iterable, enforce_sort=False, r=None):
    previous = tuple()
    if enforce_sort: # potential waste of effort (default: False)
        iterable = sorted(iterable)
    for p in permute(iterable, r):
        if p > previous:
            previous = p
            yield p

def sum_min(p):
    return sum(p), min(p)

def partitions_by_length(max_n, sorting=True, permuting=False):
    partition_dict = {0: ()}
    for n in range(1,max_n+1):
        partition_dict.setdefault(n, [])
        partitions = list(asc_int_partitions(n))
        for p in partitions:
            if permuting:
                perms = uniquely_permute(p)
                for perm in perms:
                    partition_dict.get(len(p)).append(perm)
            else:
                partition_dict.get(len(p)).append(p)
    if not sorting:
        return partition_dict
    for k in partition_dict:
        partition_dict.update({k: sorted(partition_dict.get(k), key=sum_min)})
    return partition_dict

def print_partitions_by_length(max_n, sorting=True, permuting=True):
    partition_dict = partitions_by_length(max_n, sorting=sorting, permuting=permuting)
    for k in partition_dict:
        if k == 0:
            print(tuple(partition_dict.get(k)), end="")
        for p in partition_dict.get(k):
            print(pprint_tuple(p), end=" ")
        print()
    return

def generate_powerset(items, subset_handler=tuple, verbose=False):
    """
    Generate the powerset of an iterable `items`.

    Handling of the elements of the iterable is by whichever function is passed as
    `subset_handler`, which must be able to handle the `None` value for the
    empty set. The function `string_handler` will join the elements of the subset
    with the empty string (useful when `items` is an iterable of `str` variables).
    """
    ps = {0: [subset_handler()]}
    n = len(items)
    p_dict = partitions_by_length(n-1, sorting=True, permuting=True)
    for p_len, parts in p_dict.items():
        ps.setdefault(p_len, [])
        if p_len == 0:
            # singletons
            for offset in range(n):
                subset = subset_handler([items[offset]])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        for pcount, partition in enumerate(parts):
            distance = sum(partition)
            indices = (cumsum(partition)).tolist()
            for offset in range(n - distance):
                subset = subset_handler([items[offset]] + [items[offset:][i] for i in indices])
                if verbose:
                    if offset > 0:
                        print(end=" ")
                    if offset == n - distance - 1:
                        print(subset, end="\n")
                    else:
                        print(subset, end=",")
                ps.get(p_len).append(subset)
        if verbose and p_len < n-1:
            print()
    return ps

Ví dụ, tôi đã viết một chương trình Demo CLI lấy một chuỗi làm đối số dòng lệnh:

python string_powerset.py abcdef

⇣

a, b, c, d, e, f

ab, bc, cd, de, ef
ac, bd, ce, df
ad, be, cf
ae, bf
af

abc, bcd, cde, def
abd, bce, cdf
acd, bde, cef
abe, bcf
ade, bef
ace, bdf
abf
aef
acf
adf

abcd, bcde, cdef
abce, bcdf
abde, bcef
acde, bdef
abcf
abef
adef
abdf
acdf
acef

abcde, bcdef
abcdf
abcef
abdef
acdef

abcdef