c++查找满足给定条件的前N个自然数的排列

假设我们有两个整数 N 和 K，并且我们必须查找前 N 自然数的排列 P，以便正好有满足条件 GCD（P=i、i）=1 的所有 1= i = N 的 K 元素。因此，当 N = 3 和 K = 1 时，输出将为 2、1、3。和 gcd（2， 1） = 1， gcd（1， 2） = 1， gcd（3， 3） = 3

方法很简单，我们将最后k个元素保留在其位置，其余元素移动，这样第i个元素将被放置在第（i + 1）个位置，第(N-K)个元素将被保留在 位置1，因为gcd（x，x + 1）= 1。

示例

#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
   int permutation[n + 1];
   for (int i = 1; i <= n; i++)
   permutation[i] = i;
   for (int i = 1; i < n - k; i++)
   permutation[i + 1] = i;
   permutation[1] = n - k;
   for (int i = 1; i <= n; i++)
   cout << permutation[i] << " ";
}
int main() {
   int n = 5, k = 2;
   cout << "排列是: ";
   findPermutation(n, k);
}

输出结果

排列是: 3 1 2 4 5