同じものを含む順列
説明
たとえば、a,a,b,b,b,c,d の7つの文字を一列に並べて順列を作る
この場合、並べる物に同一の物が含まれていて区別できない
既に選ばれたものを並べ替える、とも言える
𝑛 個の中に同じものが 𝑝 個、𝑞 個、𝑟 個・・・ずつあるとき、その並べ方の総数は
n! / p! * q! * r!
置き場所を選んで、「組合せ」として解くこともできる
nCp * n-1Cq
このとき、n = p + q + r
最短経路問題も、これで解くことができる
サンプル
"A", "B", "B", "C"から2つ選んで並べる
"AB", "AC", "BA", "BB", "BC", "CA", "CB"
コード
同じ物を含む順列の列挙:再帰
https://paiza.io/projects/RwoyHv2T36svGflpP7nupg
参考ページ
場合の数|同じものを含む順列について | 日々是鍛錬 ひびこれたんれん
https://hibikore-tanren.com/permutation-samething/
同じものを含む順列の公式 意味と使い方 | | 高校数学の知識庫
http://math-souko.jp/%E5%90%8C%E3%81%98%E3%82%82%E3%81%AE%E3%82%92%E5%90%AB%E3%82%80%E9%A0%86%E5%88%97%E3%81%AE%E5%85%AC%E5%BC%8F%E3%80%80%E6%84%8F%E5%91%B3%E3%81%A8%E4%BD%BF%E3%81%84%E6%96%B9/
同じものを含む順列と組合せは”同じ”です【問題4選もあわせて解説】 | 遊ぶ数学
https://integraldx.info/permutations-with-repetition-3764
#順列・組み合わせ