シーヶンスコンポジット播種機

並べ替えと組合せ
整列

秩序化組合せ

順序が異なる、処理

コンポジット
順序を考慮せずに

を選択

要素は同じであるが、順序の異なる繰り返しは許されない

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=449&sca=2080
サイコロ投げ回数Nと出力フォーマットMを入力し、Mの値に応じて以下の出力プログラムをそれぞれ作成してください.

繰り返し順

の順序(順序が異なる場合は処理が異なる)があり、要素

を繰り返すことができる.

N回サイコロ(繰り返し順)

を投げる

def dice1(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(1, 7):
        path[cnt] = str(i)
        dice(cnt + 1, type, start)
path = [""] * 100
dice1(0, 1)

整列

順序は

であり、繰り返し要素X

を許容する.

N回サイコロを投げ、発生する可能性のあるすべての状況(シーケンス)

アクセス

を確認する必要があります.

def comb(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(start, 7):
        path[cnt] = str(i)
        comb(cnt + 1, i)
path = [""] * 100
visit = [0] * 8
N = 3
comb(0, 1)

コンポジット

順序なし(順序が異なるが元素が同じ子供x)繰り返し元素X

を許容する.

N回のサイコロを投げ、異なる数の場合(組合せ)

が発生する可能性がある.

から出る場合は、アクセスを0にリセットする必要があります.

def dice3(cnt, start):
    if cnt == N:
        print(*path)
        return
    for i in range(1, 7):
        if visit[i]: continue
        visit[i] = 1
        path[cnt] = str(i)
        dice(cnt + 1, type, start)
        visit[i] = 0
path = [""] * 100
visit = [0] * 8
dice3(0, 1)

💡

backtrackingは、完全に探索で使われているので、よく理解しておきましょう!!
基本功の重要性!