C++에서 주어진 조건을 만족하는 처음 N개의 자연수의 순열 찾기

두 개의 정수 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