Python에서 배열의 가능한 모든 세트 파티션을 생성하는 방법은 무엇입니까?

DDD
풀어 주다: 2024-11-05 13:56:02
원래의
271명이 탐색했습니다.

How to Generate All Possible Set Partitions of an Array in Python?

Python에서 파티션 설정

배열을 각 요소가 정확히 하나의 하위 집합에 속하는 별개의 하위 집합으로 나누는 것을 집합 분할이라고 합니다. 요소 배열이 있는 경우 Python을 사용하여 가능한 모든 집합 파티션을 어떻게 생성할 수 있습니까?

배열 [1, 2, 3]을 생각해 보세요. 우리는 다음과 같은 파티션을 얻는 것을 목표로 합니다:

[[1], [2], [3]]
[[1, 2], [3]]
[[1], [2, 3]]
[[1, 3], [2]]
[[1, 2, 3]]
로그인 후 복사

재귀 솔루션

우리 솔루션은 이러한 파티셔닝을 달성하기 위해 재귀를 활용합니다. n-1개 요소로 구성된 파티션의 경우 n번째 요소를 수용하기 위한 두 가지 옵션을 고려합니다.

  1. 기존 하위 집합에 n번째 요소를 추가합니다.
  2. 다음 요소만 포함하는 새 하위 집합 생성 n번째 요소입니다.

이러한 옵션을 반복적으로 적용하면 가능한 모든 파티션을 구성할 수 있습니다.

구현

<code class="python">def partition(collection):
    if len(collection) == 1:
        yield [collection]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # Insert first into existing subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n+1:]
        # Create a new subset
        yield [[first]] + smaller


something = list(range(1, 5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))</code>
로그인 후 복사

출력

1 [[1, 2, 3, 4]]
2 [[1], [2, 3, 4]]
3 [[1, 2], [3, 4]]
4 [[1, 3, 4], [2]]
5 [[1], [2], [3, 4]]
6 [[1, 2, 3], [4]]
7 [[1, 4], [2, 3]]
8 [[1], [2, 3], [4]]
9 [[1, 3], [2, 4]]
10 [[1, 2, 4], [3]]
11 [[1], [2, 4], [3]]
12 [[1, 2], [3], [4]]
13 [[1, 3], [2], [4]]
14 [[1, 4], [2], [3]]
15 [[1], [2], [3], [4]]
로그인 후 복사

이 솔루션은 주어진 배열의 가능한 모든 세트 파티션을 효과적으로 생성합니다.

위 내용은 Python에서 배열의 가능한 모든 세트 파티션을 생성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿