同じものを含む順列の生成と数

同じものを含む順列(distinct_permutations)

結構よく使うけど自分で作ると実装に工夫が必要なのでmore_itertoolsのdistinct_permutationsを使うと簡単です。

from more_itertools import distinct_permutations

for p in distinct_permutations('1122'):
    print(''.join(p))
#1122
#1212
#1221
#2112
#2121
#2211

同じものを含む順列の数

もちろんdistinct_permutationsを数えても良いのですが、もう少し効率よく以下の手順で。

• ソート ⇒ ランレングス ⇒ 全体の階乗をランレングスの階乗で割る

from math import factorial as fct
def rl(a):  # run length of the list 
  a.sort()
  ret, l = [], 1
  for i in range(1,len(a)):
    if a[i] != a[i-1]:
      ret.append(l)
      l = 1
    else: l += 1
  ret.append(l)
  return ret

def dperm(rl): # run length --> number of distinct permutations
  ret = fct(sum(rl))
  for r in rl:
    ret //= fct(r)
  return ret 

lst = [6, 3, 2,  3, 6]
print(lst, rl(lst), dperm(rl(lst)))
# [6, 3, 2, 3, 6] [1, 2, 2] 30

ランレングスをCounterで求める

PythonのCounterを使えば求まりますね。dpermも1 lineにしてみました。

from math import factorial, prod
from collections import Counter

def dperm(rl): # run length --> number of distinct permutations
  return factorial(sum(rl)) // math.prod([factorial(r) for r in rl])

lst = [6, 3, 2, 3, 6]
rl = list(Counter(lst).values())
print(lst, rl, dperm(rl))
# [6, 3, 2, 3, 6] [2, 2, 1] 30

このアルゴリズムはProject Euler: Problem 240を解くのに役に立ちます。

（開発環境：Google Colab）