T01833: 排列

implementation , http://cs101.openjudge.cn/pctbook/T01833/

大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如 n=3 时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。

任务描述：给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

输入

第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。

输出

对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。

样例输入

3
3 1
2 3 1
3 1
3 2 1
10 2	
1 2 3 4 5 6 7 8 9 10

样例输出

3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10

来源

qinlu@POJ

这三个题目是相同的，tags: implementation

01833:排列

http://cs101.openjudge.cn/practice/01833/

02996:选课

http://cs101.openjudge.cn/practice/02996/

31.下一个排列

https://leetcode.cn/problems/next-permutation/

思路一：字典序

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
Swap s[i] with s[j].
Reverse the order of all of the elements after index i till the last element.

即：

1）从后往前找第一组相邻的升序数对，记录左边的位置p。 2）从后往前找第一个比p位置的数大的数，将两个数交换。 3）把p位置后所有数字逆序。

举例：

1.从数列的右边向左寻找连续递增序列, 例如对于：1,3,5,4,2，其中5-4-2即为递增序列。

2.从上述序列中找一个比它前面的数（3）大的最小数（4），并将且交换这两个数。于是1,3,5,4,2->1,4,5,3,2，此时交换后的依然是递增序列。

3.新的递增序列逆序，即：1,4,5,3,2 => 1,4,2,3,5

python

from typing import List


def nextPermutation(nums: List[int]) -> None:
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while j >= 0 and nums[i] >= nums[j]:
            j -= 1
        
        nums[i], nums[j] = nums[j], nums[i]
    
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1


# =============================================================================
# n = int(input())
# m = int(input())
# arr = list(map(int, input().split()))
# for k in range(m):
#     nextPermutation(arr)
# print(*arr)
# =============================================================================

m = int(input())
for _ in range(m):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    for _ in range(k):
        nextPermutation(a)

    print(*a)

2022fall-cs101，陈修安

python

for i in range(int(input())):
    n, k = map(int, input().split())
    arr = [int(x) for x in input().split()]
    for j in range(k):
        for m in range(1, n):
            if arr[-m-1] < arr[-m]:
                for q in range(1, m+1):
                    if arr[-q] > arr[-m-1]:
                        arr[-m-1], arr[-q] = arr[-q], arr[-m-1]
                        arr = arr[:-m] + sorted(arr[-m:])
                        break
                break
        else:
            arr = list(range(1, n+1))
    print(' '.join(map(str, arr)))

python

#2022fall-cs101，周靖杰

n=int(input())
for i in range(n):
    m,k=map(int,input().split())
    s=[int(x) for x in input().split()]
    for i in range(k):
        t=0
        for f in range(-1,-(m-1),-1):
            if s[f-1]<s[f]:
                t=1
                break
        if t:
            q=s[m+f-1:]
            M=s[m+f-1]
            q.sort()
            u=q[q.index(M)+1]
            q.remove(u)
            q.insert(0,u)
            s=s[:m+f-1]+q
        else:s.sort()
    print(" ".join([str(c) for c in s]))

思路二：康托展开

python

# 2022fall-cs101，陈勃宇
# cantor expansion

aa = [1]
c = 1
for i in range(1,1025):
    c = c * i
    aa.append(c)

for _ in range(int(input())):
    n,k = map(int,input().split())
    *cc, = map(int,input().split())
    *bb, = range(1,n + 1)
    
    d = 0
    l = n - 1
    for j in cc:
        d = d + bb.index(j) * aa[l]
        bb.remove(j)
        l -= 1
    
    d += k
    while d >= aa[n]:
        d -= aa[n]
        
    dd = []
    *bb, = range(1,n + 1)
    for p in range(n - 1,-1,-1):
        t = d // aa[p]
        dd.append(bb[t])
        del(bb[t])
        d -= t * aa[p]
    print(*dd)

T01833: 排列 ​

T01833: 排列