집합으로부터 특정 개수 꺼내는 모든 패턴을 구한다

9609 단어 파이썬알고리즘

개요



5개 집합에서 3개 꺼낸 소집합 전체 패턴을 내보내는 알고리즘을 구합니다.
여기 를 참고했습니다.

(추기)
편리한 라이브러리가 있으므로 그쪽을 사용합시다. 가르쳐 주셔서 감사합니다.
from itertools import combinations
list(combinations([1,2,4,3],3))
>>[(1, 2, 4), (1, 2, 3), (1, 4, 3), (2, 4, 3)]

사용 언어는 파이썬입니다.

알고리즘



2개에서 3개 꺼내는 모든 패턴(꺼내도 사라지지 않는 경우)


"choice"라는 전체 집합에서 하나 꺼내는 함수를 만듭니다.
"choice"로 1개 꺼내면, depth를 1개 늘려, "choice"를 또 부릅니다. depth가 꺼내는 개수에 도달하면 돌아옵니다.
이제 모든 패턴을 생성할 수 있습니다.

꺼내 사라지는 경우, "choice"를 실행하면, 다음의 "choice"에는 선택한 녀석을 제외한 전체 집합을 건네주면 좋을 것입니다.

하나의 문제는 이것입니다.
[빨간색, 녹색], [녹색, 빨간색] 같은 패턴이 섞여 버리는 문제가 있습니다.
여기는 어쩔 수 없기 때문에, 같은 요소가 없는지 확인해, 있는 경우 한쪽을 삭제합니다.
더 좋은 방법이 있으면 알려주세요.

프로그램



import copy

class Allpattern():
    def __init__(self,n,r):
        self.n = n  #n このうち rこ 取り出す全パターン
        self.r = r
        self.pattern = []
        used = [0] * self.n
        hoge =[]
        for i in range(r):
            hoge.append(used)

    def make(self):
        """
        list1 = [1 , ・・・・ , n] という全体集合を作る
        """
        list1=[]
        for i in range(self.n):
            list1.append(i+1)

        """
        choice_list : choiceしたものを入れるリスト
        depth       : choiceっした回数
        """
        choice_list = []
        depth = 0
        self.choice(list1,depth,choice_list)

    def choice(self,list1,depth,choice_list):
        for i in list1:
            list2 = copy.deepcopy(list1)
            list2.remove(i)                           #一回選んだものは二度と選ばない
            choice_list2 = copy.deepcopy(choice_list)
            choice_list2.append(i)
            if depth+1 >= self.r:
                self.work(choice_list2)
            else:
                self.choice(list2,depth+1,choice_list2)

    def work(self,choice_list):
        """
        rコの選択が終わったとき呼び出される。
        """        
        choice_list.sort()
        if self.pattern.count(choice_list) == 0:
            self.pattern.append(choice_list)

    def disp(self):
        for i in self.pattern:
            print(i)

if __name__ == '__main__' :
    hoge = Allpattern(5,3)
    hoge.make()
    hoge.disp()



실행 결과
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

좋은 웹페이지 즐겨찾기