概要
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)]
使用言語はpythonです。
アルゴリズム
2コから3コ取り出す全パターン(取り出しても消えない場合)
"choice”という全体集合から１つ取り出す関数を作ります。
"choice"で１つ取り出したら、depthを１つ増やして、"choice”をまた呼びます。depthが取り出す個数に達したら、帰ってきます。
これで、全パターンが生成できます。
取り出して消える場合は、"choice"を実行したら、次の"choice"には選んだヤツを除いた全体集合を渡せばよいでしょう。
一つ問題なのは、これだと
[赤、緑] 、[緑 、赤] という同じパターンが混ざってしまう問題があります。
ここは仕方ないので、同じ要素がないか確認し、有った場合片方を削除します。
もっと良い方法があれば教えてください。
プログラム
import copy
class Allpattern():
def __init__(self,n,r):
self.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]