输出全排列 (20 分)

输出全排列 (20 分)

请编写程序输出前n个正整数的全排列（3<=n<=7），按字典序输出。

输入格式:
一行输入正整数n。
输出格式:
按字典序输出1到n的全排列。每种排列占一行，数字间无空格。

输入样例:
在这里给出一组输入。例如：
3
输出样例:
在这里给出相应的输出。例如：
123
132
213
231
312
321

'''
字典序如下:

设P是1~n的一个全排列:pn=p1p2...pj-1pjpj+1...pk-1pkpk+1...pn

1)从排列的右端开始，找出第一个比右边数字小的数字的序号j(j从左端开始计算)
  即 j=max{i|pi<pi+1}

2)在pj的右边的数字中，找出所有比pj大的数中最小的数字pk
  即 k=max{i|pi>pj}(右边的数从右至左是递增的，
  因此k是所有大于pj的数字中序号最大者)

3)对换pj，pk

4)再将pj+1......pk-1pkpk+1......pn倒转得到排列
p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。
'''
def r_find_firstmin(n_list):
    j = 0
    for i in range(len(n_list)-1, 0, -1):
        if n_list[i-1] < n_list[i]:
            j = i-1
            break
    return j
def find_rlistmax_min(n_list,j):
    min_k = 0
    for k in range(j+1,len(n_list)):
        if n_list[k] > n_list[j] and (min_k > n_list[k] or min_k == 0):
            min_k = n_list[k]

    return n_list.index(min_k)



#获取数字n
n = int(input())
#get the progression
n_list = [i for i in range(1,n+1)]
n_last = sorted(n_list, reverse=True)
i = 0
while True:
    if n_list == n_last:
        print(*n_list,sep="")
        break
    print(*n_list,sep="")
    j = r_find_firstmin(n_list)
    k = find_rlistmax_min(n_list,j)
    n_list[j],n_list[k] = n_list[k],n_list[j]
    n_list = n_list[:j+1]+n_list[n-1:j:-1]