정확한 n 개의 요소가 집합의 모든 하위 집합을 어떻게 사용할 수 있습니까?

정확한 n 개의 요소가 집합의 모든 하위 집합을 어떻게 사용할 수 있습니까?

---

저는 어떤 순서의 모든 가능한 부분 집합 (예 : m) 에서 함수를 테스트하기 요소 (| S | = n)가 있는 집합 S이 주어져야한다는 것을 의미합니다. . 요소 수). 답을 사용하여 부분 솔루션을 생성 한 다음 m = n이 될 때까지 다음 순서 m = m + 1로 다시 시도합니다.nm

다음과 같은 형식의 솔루션을 작성하는 중입니다.

def findsubsets(S, m):
    subsets = set([])
    ...
    return subsets

하지만 이미 알면서 이미 해결책이있을 것입니다.

이를 수행하는 가장 좋은 방법은 무엇입니까?

---

itertools.combinations 는 Python 2.6 이상을 사용하는 경우 친구입니다. 의미 링크에서 동등한 기능의 구현을 확인하십시오.

import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))

S : 부분 집합을 찾고자하는 집합
m : 부분 집합에있는 요소의 수

---

canonical 함수를 사용하여 itertools 레시피 페이지 에서 powerset 을 가져옵니다 .

from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    # note we return an iterator rather than a list
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))

다음과 같이 사용 :

>>> list(powerset("abc"))
[(), ('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')]

>>> list(powerset(set([1,2,3])))
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

원하는 경우 집합에 매핑하여 결합, 교차 등을 사용할 수 있습니다.

>>> map(set, powerset(set([1,2,3])))
[set([]), set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])]

>>> reduce(lambda x,y: x.union(y), map(set, powerset(set([1,2,3]))))
set([1, 2, 3])

---

다음은 주어진 길이의 부분 집합뿐 아니라 [0..n]의 모든 부분 집합을 제공하는 한 줄짜리입니다.

from itertools import combinations, chain
allsubsets = lambda n: list(chain(*[combinations(range(n), ni) for ni in range(n+1)]))

그래서 예

>> allsubsets(3)
[(), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)]

---

다음은 의사 코드입니다. 각 호출에 대한 값을 저장하고 호출 값이 이미 있는지 확인하기 전에 재귀 호출에 대한 값을 저장하여 동일한 재귀 호출을 잘라낼 수 있습니다.

다음 알고리즘에는 빈 집합이 있으며 모든 하위 집합이 있습니다.

list * subsets(string s, list * v) {

    if(s.length() == 1) {
        list.add(s);    
        return v;
    }
    else
    {
        list * temp = subsets(s[1 to length-1], v);
        int length = temp->size();

        for(int i=0;i<length;i++) {
            temp.add(s[0]+temp[i]);
        }

        list.add(s[0]);
        return temp;
    }
}

예를 들어 s = "123"이면 출력은 다음과 가변적입니다.

1
2
3
12
13
23
123

---

사용하지 않고itertools :

Python 3에서는 yield frombuit-in set클래스에 하위 집합 생성기 메서드를 추가하는 데 사용할 수 있습니다 .

class SetWithSubset(set):
    def subsets(self):
        s1 = []
        s2 = list(self)

        def recfunc(i=0):            
            if i == len(s2):
                yield frozenset(s1)
            else:                
                yield from recfunc(i + 1)
                s1.append(s2[ i ])
                yield from recfunc(i + 1)
                s1.pop()

        yield from recfunc()

예를 들어 아래 스 니펫은 예상대로 작동합니다.

x = SetWithSubset({1,2,3,5,6})
{2,3} in x.subsets()            # True
set() in x.subsets()            # True
x in x.subsets()                # True
x|{7} in x.subsets()            # False
set([5,3]) in x.subsets()       # True - better alternative: set([5,3]) < x
len(x.subsets())                # 32

---

이해하기 쉬운 알고리즘을 사용한 깔끔한 방법이 있습니다.

import copy

nums = [2,3,4,5]
subsets = [[]]

for n in nums:
    prev = copy.deepcopy(subsets)
    [k.append(n) for k in subsets]
    subsets.extend(prev)

print(subsets) 
print(len(subsets))

# [[2, 3, 4, 5], [3, 4, 5], [2, 4, 5], [4, 5], [2, 3, 5], [3, 5], [2, 5], [5], 
# [2, 3, 4], [3, 4], [2, 4], [4], [2, 3], [3], [2], []]

# 16 (2^len(nums))

---

$ python -c "import itertools; a=[2,3,5,7,11]; print sum([list(itertools.combinations(a, i)) for i in range(len(a)+1)], [])" [(), (2,), (3,), (5,), (7,), (11,), (2, 3), (2, 5), (2, 7), (2, 11), (3, 5), (3, 7), (3, 11), (5, 7), (5, 11), (7, 11), (2, 3, 5), (2, 3, 7), (2, 3, 11), (2, 5, 7), (2, 5, 11), (2, 7, 11), (3, 5, 7), (3, 5, 11), (3, 7, 11), (5, 7, 11), (2, 3, 5, 7), (2, 3, 5, 11), (2, 3, 7, 11), (2, 5, 7, 11), (3, 5, 7, 11), (2, 3, 5, 7, 11)]

참고 URL : https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements