トーナメントの全ての組み合わせについて

Question

8人トーナメントでの全ての組み合わせを出力したいのですが、いいアイデアが思いつきません。順列から徐々に減らしていこうとも思いましたが、非効率だなと思いました。総数は315であることはわかっています。pythonかc言語で回答してくださると嬉しいです。よろしくお願いします。
追記

import itertools
i=0
list2=[]
list3=[]
list4=[]
list5=[]
list6=[]
l = [1,2,3,4]
list1=list(itertools.permutations(l,4))
#print(list1)
print()

for i in range(24):
    list2+=[[list1[i][:2],list1[i][2:4]]]
#print(list2)
print()

for k in range(24):
    for l in range(2):
        list3+=sorted(list2[k][l])
#print(list3)
print()

for n in range(0,24*4-3,4):
    list4+=[((list3[n],list3[n+1]),(list3[n+2],list3[n+3]))]
#print(list4)
print()

for m in range(24):
    list5+=sorted(list4[m])
#print(list5)
print()

for o in range(0,45,2):
    list6+=[(list5[o],list5[o+1])]
#print(list6)
set(list6)

import itertools
list2=[]
list3=[]
list4=[]
list5=[]
list6=[]
list7=[]
list8=[]
list9=[]
list10=[]
list11=[]
list12=[]
a = [1,2,3,4,5,6,7,8]
list1=list(itertools.permutations(a,8))
#print(list1)
print()

for i in range(40320):
    list2+=[[list1[i][:4],list1[i][4:8]]]
#print(list2)
print()

for k in range(40320):
    for l in range(2):
        list3+=[[list2[k][l][:2],list2[k][l][2:4]]]
#print(list3)

for s in range(80640):
    for t in range(2):
        list4+=sorted(list3[s][t])
#print(list4)

for x in range(0,40320*8-7,8):
    list5+=[([(list4[x],list4[x+1]),(list4[x+2],list4[x+3])],[(list4[x+4],list4[x+5]),(list4[x+6],list4[x+7])])]
#print(list5)

for p in range(40320):
    for q in range(2):
        list6+=sorted(list5[p][q])
#print(list6)

for g in range(0,40320*4-3,4):
    list7+=[(list6[g],list6[g+1]),(list6[g+2],list6[g+3])]
#print(list7)

for s in range(40320*2):
    for t in range(2):
        for u in range(2):
            list8+=[list7[s][t][u]]
#print(list8)

for y in range(0,40320*8-7,8):
     list9+=[((list8[y],list8[y+1],list8[y+2],list8[y+3]),(list8[y+4],list8[y+5],list8[y+6],list8[y+7]))]
#print(list9)

for h in range(40320):
    list10+=sorted(list9[h])
#print(list10)

for s in range(40320*2):
    for t in range(4):
            list11+=[list10[s][t]]
#print(list11)

for z in range(0,40320*8-7,8):
     list12+=[((list11[z],list11[z+1]),(list11[z+2],list11[z+3]),(list11[z+4],list11[z+5]),(list11[z+6],list11[z+7]))]
#print(list12)
set(list12)

一応プログラムとしては4人の場合を考えて、無理やり8人に変えたのを製作しています。しかし、あまりにも無理やりで汚すぎたので、投稿してみました。

Comments

[dodox86]

質問者さんが思い付いたアイデアについて、「良い／悪い」、「効率的／非効率的」は置いておいて、まずはとにかく目的のものを作ってみてはいかがでしょうか。「このように作って動いていますが、こういう問題がでました。」とのような質問になれば丸投げにもならず、また、回答もあろうかと思います。

[Lycoris]

自分で考えたプログラムが無理やり過ぎたので、質問してみました。

[dodox86]

質問への追記、ありがとうございます。既にご自分のプログラムも追記で提示され、複数の回答もいただいているのでよろしいのではないかと思います。

Answer 1

こんにちは

以下のように、トーナメント参加者を、A から H とします。

上記のような場合を，リスト ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] で表すとします。

トーナメントの組み合わせを表すリストを、すべて列挙するコードの一例は以下です。（最後に、組み合わせの数も出力しています。）

import itertools


def get_matches(four_players):    
    matches = []
    for x in four_players[1:]:
        m1 = [four_players[0], x]
        m2 = [y for y in four_players[1:] if y != x]
        matches.append([*m1, *m2])
    
    return matches

        
if __name__ == '__main__':

    players = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']

    count = 0

    for block1 in itertools.combinations(players[1:], 3):
        matches1 = get_matches(['A', *block1])
        
        block2 = [x for x in players[1:] if x not in block1]
        matches2 = get_matches(block2)

        for tournament in itertools.product(matches1, matches2):
            print(sum(tournament, []))
            count += 1

    print(count)

• 動作確認用Repl.it: https://repl.it/@jun68ykt/Q267640-2

考え方としては、まず、「A は、一番左に置くことにする」と決めると分かりやすいです。

単にトーナメントの組み合わせの数を求めるのであれば、以下で算出できます。

from scipy.special import comb

result = comb(7, 3, exact=True) * comb(3, 1, exact=True) ** 2

print(result)  # => 315

• 動作確認用Repl.it: https://repl.it/@jun68ykt/Q267640

追記

リストを回転させる関数 rotate

def rotate(l, n):
    return l[n:] + l[:n]

を作っておくと、 get_matches は以下のようにも書けます。

def get_matches(four_players):
    car, *cdr = four_players
    return [[car, *rotate(cdr, i)] for i in range(len(cdr))]

• 動作確認用Repl.it: https://repl.it/@jun68ykt/Q267640-3

Comments

[Lycoris]

きれいで、丁寧な回答ありがとうございます。
一番に回答していただいたのでベストアンサーにさせていただきます。

[jun68ykt]

どういたしまして????　参考になれば幸いです。

Answer 2

pythonかc言語

当方，pythonができない＆順列の列挙処理をCで書くのが辛い　→　のでC++，
且つ，効率度外視のひどいアルゴリズムですが…

int main(void)
{
    //※8人を表す値：それぞれが異なるbitが立っている値．
    unsigned char Vals[] = { 1,2,4,8, 16,32,64,128 };

    //※関数Outputは Vals の状態に対応した出力を行う
    Output( Vals ); //初期状態を出力
    unsigned int N = 1;  //※一応カウントしてみる用

    //順列列挙ループ
    while( std::next_permutation( std::begin(Vals), std::end(Vals) ) )
    {//条件：枝分かれ箇所の左側にいる人達の値の合計が，右側の人達の値の合計よりも小さいこと
        //１回戦の段の判定
        if( Vals[0] > Vals[1] )continue;
        if( Vals[2] > Vals[3] )continue;
        if( Vals[4] > Vals[5] )continue;
        if( Vals[6] > Vals[7] )continue;
        //２回戦の段の判定
        if( (Vals[0]|Vals[1]) > (Vals[2]|Vals[3]) )continue;
        if( (Vals[4]|Vals[5]) > (Vals[6]|Vals[7]) )continue;
        //３回戦の段の判定
        if( (Vals[0]|Vals[1]|Vals[2]|Vals[3]) > (Vals[4]|Vals[5]|Vals[6]|Vals[7]) )continue;

        //ここまできたら，この並び順が新しいパターンである
        Output( Vals ); //出力
        ++N;  //カウントアップ
    }
    std::cout << N; //※カウンタの値を見てみる． 315 と表示される
    return 0;
}

とりあえず
while( std::next_permutation( std::begin(Vals), std::end(Vals) ) )
の一文を除いては，Cだと思って見てもらえば，処理内容はわかるかと．
この一文は順列の列挙処理で，
「配列Valsの要素の並び順を，次の並び順に更新する」（次が無い時点でループを終了）
をやっています．

Comments

[Lycoris]

このような考え方でもできるんですね。
ベストアンサーにしたいのですが、今回は最初に回答してくれた方をベストアンサーにさせてもらいます。回答ありがとうございました。

Answer 3

単純に、８つを総当りで組み合わせを出し、重複がないのを確認するというコードを組んでみてください。

効率や良し悪しは、それからのおはなしとなります

Comments

[Lycoris]

それも考えたのですが、どうやって左端のトーナメントで試合した組み合わせに含むチームを隣の山で除外すれば良いのかがわかりませんでした。