問題概要

正整数nに対し、1からnまでの数値で構成される順列を辞書順に並べたとき、指定された順列のk個後の順列を求める問題です。最終順列の次は最初の順列に戻る必要があります。

例

n = 3, k = 2のとき、入力が2 3 1の場合：

• 1回後の順列：3 1 2
• 2回後の順列：3 2 1

入出力仕様

入力

1行目：テストケース数m
各テストケース：
  1行目：n(1<=n<1024)とk(1<=k<=64)
  2行目：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

アルゴリズム実装

C言語

#include <stdio.h>
#include <stdlib.h>

void exchange(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void invert(int arr[], int start, int end) {
    while (start < end) {
        exchange(&arr[start], &arr[end]);
        start++;
        end--;
    }
}

void next_permutation(int sequence[], int size) {
    int idx = size - 2;
    while (idx >= 0 && sequence[idx] >= sequence[idx+1]) {
        idx--;
    }
    if (idx >= 0) {
        int j = size - 1;
        while (j >= 0 && sequence[j] <= sequence[idx]) {
            j--;
        }
        exchange(&sequence[idx], &sequence[j]);
    }
    invert(sequence, idx+1, size-1);
}

int main() {
    int cases;
    scanf("%d", &cases);
    while (cases--) {
        int n, k;
        scanf("%d %d", &n, &k);
        int nums[1024];
        for (int i=0; i<n; i++) {
            scanf("%d", &nums[i]);
        }
        
        for (int i=0; i<k; i++) {
            next_permutation(nums, n);
        }
        
        for (int i=0; i<n-1; i++) {
            printf("%d ", nums[i]);
        }
        printf("%d\n", nums[n-1]);
    }
    return 0;
}

C++

#include <iostream>
#include <algorithm>
#include <vector>

void find_next(std::vector<int> &sequence) {
    int idx = sequence.size() - 2;
    while (idx >= 0 && sequence[idx] >= sequence[idx+1]) {
        idx--;
    }
    if (idx >= 0) {
        int j = sequence.size() - 1;
        while (j >= 0 && sequence[j] <= sequence[idx]) {
            j--;
        }
        std::swap(sequence[idx], sequence[j]);
    }
    std::reverse(sequence.begin()+idx+1, sequence.end());
}

int main() {
    int m;
    std::cin >> m;
    while (m--) {
        int n, k;
        std::cin >> n >> k;
        std::vector<int> data(n);
        for (int i=0; i<n; i++) {
            std::cin >> data[i];
        }
        
        for (int i=0; i<k; i++) {
            find_next(data);
        }
        
        for (int i=0; i<n-1; i++) {
            std::cout << data[i] << " ";
        }
        std::cout << data[n-1] << std::endl;
    }
    return 0;
}