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

同じものを含む順列(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(a): # num of distinct permutation 
  ret = fct(len(a))
  for r in rl(a):
    ret //= fct(r)
  return ret 

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

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

（開発環境：Google Colab）