問題の説明

n人が一列に並んでいます.n人の番号は1番からn番までです.n個人で並ぶ方法はいろいろあります.たとえば、3人がいる場合は、次の6つの方法があります.

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]
人の数nと自然数kが与えられた場合、予め順番に人を列挙する方法を完了した場合、k回の方法の解関数を返します.

せいげんじょうけん

nは20未満の自然数である.
kはnだ!以下は自然数です.

I/O例

n	k	result
3	5	[3,1,2]

I/O例説明

I/O例#1
問題の例.

方法

最初にitertoolsの配列を使用してすべての状況を求め、ソートしてk-1インデックスにアクセスします.問題はよく解決されたが、効率考課は一つも合格しなかった.
次いで、置換を再帰関数で実装し、結果リストの長さがkより大きい場合、再帰関数を終了する.しかし、この方法もよく解決されなかった.
最後に他の人の解答を参考にして、特定のルールで解決するのを見ました.

n!求めたサイズは、nをtmpで割って格納する.

変数idxに

の結果値を入力し、結果リストに入る要素リストを保存します.

kをk//tmpに更新します.

kが0であれば、結果リストにk%tmpを入れ、0でなければnums[idx-1]を入れる.

nを1減少させる.

このプロセスを繰り返すと、n、tmp、idx、kは各反復で更新され、k番目のケースを求めることができる.

solution.py

def solution(n, k):
    answer = []
    nums=[i for i in range(1, n+1)]
    while n!=0:
        tmp=1
        for i in range(1, n):
            tmp*=i
        idx=k//tmp
        k%=tmp
        if k==0:
            answer.append(nums.pop(idx-1))
        else:
            answer.append(nums.pop(idx))
        n-=1
    return answer