python 추출 파이썬에서 파티션 설정하기




파이썬 문자열 추출 (2)

나는 [1,2,3] 배열을 가지고있다 [1,2,3]

배열의 모든 요소를 ​​사용하여 가능한 모든 조합을 만들고 싶습니다.

결과:

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

제안 된 의견과 달리, itertools 기반의 비교적 빠른 솔루션을 신속하게 찾을 수 없었습니다! 편집 : 이것은 더 이상 사실이 아닙니다. itertools를 주로 사용하는 상당히 짧은 (그러나 느리고 읽을 수없는) 해결책이 있습니다. 답변의 끝 부분을 참조하십시오. 이것은 내가 가지고있는 것입니다.

아이디어는 목록의 길이를 합한 모든 정수 조합을 찾은 다음 해당 길이의 조각으로 목록을 가져 오는 것입니다.

예를 들어 길이 3의 목록에 대해 조합 또는 파티션은 (3), (2, 1), (1, 2) 및 (1, 1, 1)입니다. 그래서 우리는 목록의 처음 세 항목을 반환합니다. 첫 번째 2 다음에 다음 1; 첫 번째 1 다음 2 다음 첫 번째 1 다음 다음 1 다음 다음 1.

here 정수 분리를위한 코드를 얻었 here . 그러나 파티션 함수는 파티션의 모든 순열을 반환하지 않습니다. 즉 3은 (3), (2, 1) 및 (1, 1, 1)을 반환 할 것이기 때문에 각각의 itertools.permutations 를 호출해야합니다. permutations([1, 2, 3])[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 같이 복제본을 제거해야합니다. permutations([1, 1, 1])[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] 이고, permutations([1, 1, 1])[[1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1]] 중복을 제거하는 쉬운 방법은 튜플의 각 목록을 set .

그런 다음 나머지는 튜플의 길이에 대한 목록의 조각을 얻는 것입니다. 예를 들어 f([1, 2, 3], [0, 0, 1, 2, 1, 0])[[0], [0, 1], [2, 1, 0]]

그것의 나의 정의는 이것이다 :

def slice_by_lengths(lengths, the_list):
    for length in lengths:
        new = []
        for i in range(length):
            new.append(the_list.pop(0))
        yield new

이제 우리는 모든 것을 결합합니다.

def subgrups(my_list):
    partitions = partition(len(my_list))
    permed = []
    for each_partition in partitions:
        permed.append(set(itertools.permutations(each_partition, len(each_partition))))

    for each_tuple in itertools.chain(*permed):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

>>> for i in subgrups(my_list):
        print(i)

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

또한, import itertools 하고 from copy import deepcopy 를 프로그램의 맨 위에서 할 필요가 있습니다.

편집 : 주어진 출력이 불분명합니다. 나는 당신에게 주어진 함수를 원했을 것이라고 추측했지만, 출력에는 [[1,3],[2]] 가 포함되어 있는데 나머지는 제안 된 출력과는 달리 출력 순서가 다릅니다. 실제로 [[1, 2], [3]] [[1, 2], 3] 원하지 않는다고 가정하는 자유를 취했습니다.

말하자면, 나는 당신이 산출물로 내놓을 것을 의미하는 것을 다음과 같이 추정합니다 :

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

실제로 사실이라면 다음과 같습니다.

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

그런 다음 itertools.permutations(my_list, len(my_list)) 각 순열에 대해 원래 목록의 각 3 길이 순열에 대해 subgrups 을 호출하기 subgrups 됩니다.

편집 : 지금은 짧은 itertools 기반 솔루션의 내 약속을 개최합니다. 경고 - 읽을 수없고 느릴 수도 있습니다.

먼저 slice_by_lengths 를 다음과 같이 slice_by_lengths .

def sbl(lengths, the_list):
    for index, length in enumerate(lengths):
        total_so_far = sum(lengths[:index])
        yield the_list[total_so_far:total_so_far+length]

그런 다음 this 대답에서 정수 분할 함수를 얻습니다.

def partition(number):
    return {(x,) + y for x in range(1, number) for y in partition(number-x)} | {(number,)}

이 함수는 실제로 우리를 위해 정수 파티션의 모든 순열을 얻습니다. 그래서 우리는 필요하지 않습니다.

for each_partition in partitions:
    permed.append(set(itertools.permutations(each_partition, len(each_partition))))

더 이상. 그러나 재귀 적이기 때문에 이전에했던 것보다 훨씬 느립니다 (파이썬에서 구현하고 있습니다).

그런 다음 함께 정리하면됩니다.

def subgrups(my_list):
    for each_tuple in partition(len(my_list)):
        yield list(slice_by_lengths(each_tuple, deepcopy(my_list)))

또는 덜 읽을 수 있지만 함수 정의가없는 경우

def subgrups(my_list):
    for each_tuple in (lambda p, f=lambda n, g:
                          {(x,) + y for x in range(1, n) for y in g(n-x, g)} | {(n,)}:
                              f(p, f))(len(my_list)):
        yield list(my_list[sum(each_tuple[:index]):sum(each_tuple[:index])+length] for index, length in enumerate(each_tuple))

어떤 함수 정의와 두 줄, 그래서 내가 원래 (훨씬 덜 읽을 수 있지만 훨씬 느린) 명시된 닫습니다!

(질문은 처음에 "모든 서브 그룹"을 찾았 기 때문에 subgrups 이라고하는 함수)


이 멋진 질문이 다시 생생 해 졌으니 여기 새로운 대답이 있습니다.

문제는 재귀 적으로 해결됩니다. 이미 n-1 개 요소의 파티션이 있다면 n 개 요소를 분할하는 데 어떻게 사용합니까? 기존의 부분 집합 중 하나에 n 번째 요소를 배치하거나 새로운 단일 부분 집합으로 추가하십시오. 그게 전부입니다. itertools , no set, 반복 된 출력 없음 및 partition() 대한 총 n itertools 호출 총계 :

def partition(collection):
    if len(collection) == 1:
        yield [ collection ]
        return

    first = collection[0]
    for smaller in partition(collection[1:]):
        # insert `first` in each of the subpartition's subsets
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[ first ] + subset]  + smaller[n+1:]
        # put `first` in its own subset 
        yield [ [ first ] ] + smaller


something = list(range(1,5))

for n, p in enumerate(partition(something), 1):
    print(n, sorted(p))

산출:

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]]




combinatorics