同じものを含む順列
説明
たとえば、a,a,b,b,b,c,d の７つの文字を一列に並べて順列を作る
この場合、並べる物に同一の物が含まれていて区別できない
既に選ばれたものを並べ替える、とも言える
𝑛 個の中に同じものが 𝑝 個、𝑞 個、𝑟 個・・・ずつあるとき、その並べ方の総数は
n! / p! * q! * r!
置き場所を選んで、「組合せ」として解くこともできる
nCp * n-1Cq
このとき、n = p + q + r
最短経路問題も、これで解くことができる
サンプル
"A", "B", "B", "C"から2つ選んで並べる
"AB", "AC", "BA", "BB", "BC", "CA", "CB"
コード
同じ物を含む順列の列挙：再帰
参考ページ
場合の数｜同じものを含む順列について | 日々是鍛錬 ひびこれたんれん
同じものを含む順列の公式 意味と使い方 | | 高校数学の知識庫
同じものを含む順列と組合せは”同じ”です【問題４選もあわせて解説】 | 遊ぶ数学