同じものを含む順列の辞書式の順番を求める

[【Project Euler】Problem 24: 辞書式順列](https://qiita.com/masa0599/items/e2d0ead2a8d7df7a59d0)では順列の辞書式の順番を求めましたが、今回は同じものを含む順列で順番を考えます。

### １．distinct_permutationsを使う

**【例題１】1を1個、3を3個、5を5個使って9桁の数を作って昇順並べたとき100番目の数を求めよ**

まずdistinct_permutationsで順番に生成して100番目を求めます。

```python 
from more_itertools import distinct_permutations
for cnt, p in enumerate(distinct_permutations("133355555"),1):
  if cnt >= 100:
    break
print(f"Answer: {''.join(p)}")
Answer: 335513555
```

### ２．最上位桁から固定してブロックの数を積算する

[【Project Euler】Problem 24: 辞書式順列](https://qiita.com/masa0599/items/e2d0ead2a8d7df7a59d0)の「より効率の良い解答」のコードを「同じものを含む順列」に以下のポイントで書き換えます。

1. 使う数[1,3,5]とその使える個数[1,3,5]のリストを用意する
1. 順列の個数（math.factorial）を同じものを含む順列の個数（dperm）に変更する。dpermは[同じものを含む順列の生成と数](https://qiita.com/masa0599/items/d03391e0d01c28d84760)で作ったコードを使います

これで１．と同じ答えを得ることが出来ました

```python 
from copy import copy
nl = [1,3,5]    # number list
un = [1,3,5]    # unused number count
def lexn(N, un):  # Remaing N, Unused number
  print(N, un)
  total = 0
  for i in range(len(un)):
    if un[i] == 0: continue
    un1 = copy(un)
    un1[i] -= 1
    d = dperm(un1)
    if total+d >= N:
      return str(nl[i]) + lexn(N-total, un1)
    total += d
  return ""

N = 10**2
print(f"Answer: {lexn(N, un)}")
# Answer: 335513555
```

### ３．数を[1,3,5,7,9]に増やす

**【例題２】例題１で[1,3,5]を[1,3,5,7,9]にして同様に昇順並べたとき$10^{12}$番目の数を求めよ**

これだけ増えても問題なく解けます

```python 
nl = [1,3,5,7,9]    # number list
un = [1,3,5,7,9]    # unused number count
:
N = 10**12
print(f"Answer: {lexn(N, sum(un), un)}")
# Answer: 3751999579973955779977593
```

### ４．使う個数は[1,3,5]のどれでも良いとする

**【例題３】例題１で[1,3,5]を[1,3,5]個のどれかを使って9桁の数を作ったときに$10^3$番目の数を求めよ。例えば111113555もOKです**

変更点のポイントは

1. 使える個数のリストは$3!=6$個あるのでこれをリストにして各々の個数を足す
1. 使用した数を各々のリストから除いて、再帰的に利用する

コードは以下のようになります。使用できる数のリスト**un**が変化していく様子も表示したので見るとなるほどと思います。

```python 
nl = [1,3,5]    # number list
un = [pm for pm in permutations(nl,3)]  # unused number count
def lexn2(N, un):  # Remaing N, Unused number
  print("#", N, un)
  total = 0
  for i in range(len(nl)):
    d, un1 = 0, []
    for unp in un:
      if unp[i] == 0: continue
      unp1 = list(unp)
      unp1[i] -= 1
      d += dperm(unp1)
      un1 += [tuple(unp1)]
    if total+d >= N:
      return str(nl[i]) + lexn2(N-total, un1)
    total += d
  return ""

N = 10**3
print(f"# Answer: {lexn2(N, un)}")
# 1000 [(1, 3, 5), (1, 5, 3), (3, 1, 5), (3, 5, 1), (5, 1, 3), (5, 3, 1)]
# 1000 [(0, 3, 5), (0, 5, 3), (2, 1, 5), (2, 5, 1), (4, 1, 3), (4, 3, 1)]
# 314 [(0, 3, 4), (0, 5, 2), (2, 1, 4), (2, 5, 0), (4, 1, 2), (4, 3, 0)]
# 108 [(0, 3, 3), (0, 5, 1), (2, 1, 3), (4, 1, 1)]
# 38 [(0, 3, 2), (0, 5, 0), (2, 1, 2), (4, 1, 0)]
# 8 [(0, 3, 1), (2, 1, 1)]
# 2 [(0, 2, 1), (2, 0, 1)]
# 2 [(1, 0, 1)]
# 1 [(1, 0, 0)]
# 1 [(0, 0, 0)]
# Answer: 155553151
```

### ５．桁数を制限しない

**【例題４】例題３と同様に[1,3,5]を[1,3,5]個のどれかを使って数を作った（桁数は制限しない）ときに$10^5$番目の数を求めよ。例えば135,5313535,31315155355もOKです。**


1.　変更点は桁の少ない順にその桁で表される個数を積算していって$10^5$を超えたときが$10^5$番目を含む桁
1.　桁数が分かったら例題３の**lexn2**に残りの数を入力


```python 
from itertools import product, permutations
un = [1,3,5]    # unused number count
und = [[]for i in range(5*3+1)]
for pm in product(un,repeat=3):  
  und[sum(pm)].append(pm)

N = 10**5
total = 0
for idx, un in enumerate(und):
  if len(un) == 0: continue
  subt = sum([dperm(unp) for unp in un])
  print(f"# {idx} digits, un={un}, total ={total+subt}")
  if total+subt> N:
    break
  total += subt

print("# ******", idx, und[idx], total)
# 3 digits, un=[(1, 1, 1)], total =6
# 5 digits, un=[(1, 1, 3), (1, 3, 1), (3, 1, 1)], total =66
# 7 digits, un=[(1, 1, 5), (1, 3, 3), (1, 5, 1), (3, 1, 3), (3, 3, 1), (5, 1, 1)], total =612
# 9 digits, un=[(1, 3, 5), (1, 5, 3), (3, 1, 5), (3, 3, 3), (3, 5, 1), (5, 1, 3), (5, 3, 1)], total =5316
# 11 digits, un=[(1, 5, 5), (3, 3, 5), (3, 5, 3), (5, 1, 5), (5, 3, 3), (5, 5, 1)], total =41352
# 13 digits, un=[(3, 5, 5), (5, 3, 5), (5, 5, 3)], total =257568
# ***** 13 digits, un=[(3, 5, 5), (5, 3, 5), (5, 5, 3)], remaining total =58648
```

まず1.を調べるコードを実行すると13桁累計$257,568$で$10^5$を超えることが分かります。従って**lexn2**に13桁の**un**と$N-41352$を入力すれば答えが得られます。

```python
print(f"# Answer: {lexn2(N-total, und[idx])}")
# Answer: 1533153115551
```

（開発環境：Google Colab）

この考え方はProject Euler、Problem698: 123 Numbersを解くのに役に立ちます。