【Project Euler】Problem 24: 辞書式順列では順列の辞書式の順番を求めましたが、今回は同じものを含む順列で順番を考えます。
１．distinct_permutationsを使う
【例題１】1を1個、3を3個、5を5個使って9桁の数を作って昇順並べたとき100番目の数を求めよ
まずdistinct_permutationsで順番に生成して100番目を求めます。
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: 辞書式順列の「より効率の良い解答」のコードを「同じものを含む順列」に以下のポイントで書き換えます。
- 使う数[1,3,5]とその使える個数[1,3,5]のリストを用意する
- 順列の個数（math.factorial）を同じものを含む順列の個数（dperm）に変更する。dpermは同じものを含む順列の生成と数で作ったコードを使います
これで１．と同じ答えを得ることが出来ました
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}$番目の数を求めよ
これだけ増えても問題なく解けます
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です
変更点のポイントは
- 使える個数のリストは$3!=6$個あるのでこれをリストにして各々の個数を足す
- 使用した数を各々のリストから除いて、再帰的に利用する
コードは以下のようになります。使用できる数のリストunが変化していく様子も表示したので見るとなるほどと思います。
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に残りの数を入力
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$を入力すれば答えが得られます。
print(f"# Answer: {lexn2(N-total, und[idx])}")
# Answer: 1533153115551
（開発環境：Google Colab）
この考え方はProject Euler、Problem698: 123 Numbersを解くのに役に立ちます。