집합으로부터 특정 개수 꺼내는 모든 패턴을 구한다
개요
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]
Reference
이 문제에 관하여(집합으로부터 특정 개수 꺼내는 모든 패턴을 구한다), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/hiRina/items/dbd815cbc699cdae74d0
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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]
Reference
이 문제에 관하여(집합으로부터 특정 개수 꺼내는 모든 패턴을 구한다), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/hiRina/items/dbd815cbc699cdae74d0
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
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]
Reference
이 문제에 관하여(집합으로부터 특정 개수 꺼내는 모든 패턴을 구한다), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/hiRina/items/dbd815cbc699cdae74d0텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)