C++で指定された条件を満たす最初のN個の自然数の順列を見つけます

2つの整数NとKがあり、すべての1 <=iに対してGCD（P [i]、i）> 1の条件を満たすK個の要素が正確に存在するように、最初のN個の自然数の順列Pを見つける必要があるとします。 <=N。したがって、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）番目の要素が保持されるようにします。 gcd（x、x + 1）=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 << "The permutation is: ";
   findPermutation(n, k);
}

出力

The permutation is: 3 1 2 4 5