問題
私のお母さんは先生です。彼女は最近、生徒のリストを取得して生徒のペアのセットを生成するスクリプトを書くように私に依頼しました。各生徒は他のすべての生徒とペアにする必要があり、生徒は同じ生徒と複数回作業することはありません。
たとえば、 、 、 の 4 人の生徒がいる"Bob"と"Lisa"し"Duke"ます"Tyrone"。スクリプトは次の出力を生成する必要があります。
{ { "Bob", "Lisa" }, { "Duke", "Tyrone" } }
{ { "Bob", "Duke" }, { "Lisa", "Tyrone" } }
{ { "Bob", "Tyrone" }, { "Lisa", "Duke" } }
素朴な試み
これは簡単なプロジェクトだと思っていましたが、コーディングの途中で、リストを生成するための効率的なアルゴリズムを作成するのは少し難しいことに気付きました。もともと、私はこの単純な実装を Ruby で書きました。
# the list of students
CLASS_LIST = ("A".."H").to_a
# add an extra element to the class list if the class list length is odd
CLASS_LIST << nil if CLASS_LIST.length.odd?
# determine all possible permutations of the class lists
permutations = CLASS_LIST.permutation
# convert all of the permutations into pairs
permutations = permutations.map { |permutation| permutation.each_slice(2).to_a }
puts "PERMUTATIONS LENGTH: " + permutations.length.to_s
# iterate through the permutations and remove all subsequent permutations that contain a matching
# pair
i = 0
while i < permutations.length
# remove any subsequent permutations that contain pairs already in the current permutation
permutations.delete_if do |permutation|
# return true if the current permutation has any elements in common with the other permutation
permutations.index(permutation) > i and permutations[i].any? do |p1|
permutation.any? do |p2|
(p1[0] == p2[0] and p1[1] == p2[1]) or (p1[0] == p2[1] and p1[1] == p2[0])
end
end
end
# increment i
i += 1
end
permutations.each do |permutation|
p permutation
end
この実装は恐ろしく非効率的でした。プロファイリングしたところ、4 人の生徒は 0.093 秒、6 人の生徒は 0.376 秒、8 人の生徒は 35 分 32 秒かかりました。さらに、順列の総数は管理不能でした。4 人の生徒には 24 の順列があり、6 人の生徒には 720、8 人の生徒には 40320 があります。
漸近的に、whileループは O(n!) でdelete_if実行され、ループは O(n!) で実行され、permutations.indexandpermutations.any?ループは O(n!) で実行され、内側のpermutation.any?ループは O(n) 時間で実行され、アルゴリズム全体が実行されます。 O(n(n!)^3)で! 明らかに、このソリューションは機能しません。
より良いアプローチ
考えられるすべてのペアをループする必要がないことに早い段階で気付きました。すべての学生は他のすべての学生と 1 回だけ作業するため、結果セットを結合すると、すべての一意の可能なペアが得られるはずです。このセットを生成することから始めることにしました。まず、考えられるすべての組み合わせを調べました。
A B C D E F
A A,A A,B A,C A,D A,E A,F
B B,A B,B B,C B,D B,E B,F
C C,A C,B C,C C,D C,E C,F
D D,A D,B D,C D,D D,E D,F
E E,A E,B E,C E,D E,E E,F
F F,A F,B F,C F,D F,E F,F
次に、学生が自分で取り組んでいたペアを削除しました。
A B C D E F
A A,B A,C A,D A,E A,F
B B,A B,C B,D B,E B,F
C C,A C,B C,D C,E C,F
D D,A D,B D,C D,E D,F
E E,A E,B E,C E,D E,F
F F,A F,B F,C F,D F,E
最後に、重複したペアを削除しました。
A B C D E F
A A,B A,C A,D A,E A,F
B B,C B,D B,E B,F
C C,D C,E C,F
D D,E D,F
E E,F
F
ペアを生成することは、Ruby ではかなり簡単でした。
# generate the set of all possible pairs
UNIQUE_PAIRS = (0..(CLASS_LIST.length - 2)).to_a.map do |row|
((row + 1)..(CLASS_LIST.length - 1)).to_a.map do |column|
[ row, column ]
end
end.flatten(1)
次に、これらの一意のペアを探している結果セットに変換する方法を見つけようとしました。私のアイデアは、各リストに可能なすべてのペアのセットを作成し、ペアが各リストに追加されたときに使用できなかったペアを削除することでした。最初の試みでは、次のリストに進む前に各リストに記入しようとしました。
STEP 0:
LIST 1: { }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, B }, { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 1:
LIST 1: { { A, B } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 2:
LIST 1: { { A, B }, { C, D } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 3:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
STEP 4:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { { A, C } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F } }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
STEP 5:
LIST 1: { { A, B }, { C, D }, { E, F } }
LIST 2: { { A, C }, { B, D } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { }
AVAILABLE 2: { }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { D, E }, { D, F } }
使用可能なペアが残っていないため、これはステップ 6 で失敗します。次に、アルゴリズムを逆方向に実行してみました。
STEP 1:
LIST 1: { { A, B } }
LIST 2: { }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, C }, { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 2:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 4: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, D }, { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 3:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { }
LIST 5: { }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 5: { { A, E }, { A, F }, { B, C }, { B, D }, { B, E }, { B, F }, { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
STEP 4:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, D }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, D }, { C, E }, { D, E } }
STEP 5:
LIST 1: { { A, B } }
LIST 2: { { A, C } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { C, D }, { C, E }, { C, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 2: { { B, D }, { B, E }, { B, F }, { D, E }, { D, F }, { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, D }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, D }, { C, E }, { D, E } }
STEP 6:
LIST 1: { { A, B }, { C, D } }
LIST 2: { { A, C }, { B, D } }
LIST 3: { { A, D } }
LIST 4: { { A, E } }
LIST 5: { { A, F } }
AVAILABLE 1: { { E, F } }
AVAILABLE 2: { { E, F } }
AVAILABLE 3: { { B, C }, { B, E }, { B, F }, { C, E }, { C, F }, { E, F } }
AVAILABLE 4: { { B, C }, { B, D }, { B, F }, { C, F }, { D, F } }
AVAILABLE 5: { { B, C }, { B, D }, { B, E }, { C, E }, { D, E } }
ステップ 6 の後、アルゴリズムが失敗することは明らかです。
次は何ですか？
ここで私が見逃している数学的原理が明らかにあります。これを行う正しい方法は何ですか？事前に助けてくれてありがとう！