N 정수를 포함하는 배열 a[]가 주어지면 해당 인덱스의 값이 감소하지 않는 시퀀스를 형성하도록 k개의 다른 인덱스 순열을 인쇄하는 것이 과제입니다. 불가능한 경우 -1을 출력합니다.
예시
Input: arr[] = {2,5,6,2,2,2,2}, k = 4
Output:
0 3 4 5 6 1 2
3 0 4 5 6 1 2
0 3 4 5 6 1 2
3 0 4 5 6 1 2 주어진 배열을 정렬하고 각 요소의 원래 인덱스를 추적합니다. 이것은 하나의 필수 순열을 제공합니다. 이제 2개의 연속 요소가 같으면 다른 순열을 얻기 위해 교체할 수 있습니다. 마찬가지로 세 번째 순열이 생성될 수 있습니다.
알고리즘
START
Step 1 -> Declare Function void indice(int n, pair<int, int> array[])
Loop For int i=0 and i<n and i++
Print array[i].second
End
Step 2 -> Declare Function void permutation(int n, int a[], int k)
Use STL pair<int, int> arr[n]
Loop for int i=0 and i<n and i++
Set arr[i].first = a[i]
Set arr[i].second = i
End
Call sort(arr, arr + n)
Declare int count to 1
Loop For int i=1 and i<n and i++
IF (arr[i].first == arr[i - 1].first)
Increment count by 1
End
End
IF count < k
Return -1
End
Loop For int i = 0 and i < k – 1 and i++
Call indice(n, arr)
Loop For int j = 1 and j < n and j++
IF arr[j].first == arr[j - 1].first
Call swap(arr[j], arr[j - 1])
Break
End
End
End
Call indice(n, arr)
Step 3 -> In main()
Declare array a[]={2,5,6,2,2,2,2}
Declare int n= sizeof(a)/sizeof(a[0])
Declare int k=4
Call permutation(n,a,k)
STOP 예시
#include <bits/stdc++.h>
using namespace std;
void indice(int n, pair<int, int> array[]){
for (int i = 0; i < n; i++)
cout << array[i].second << " ";
cout << endl;
}
void permutation(int n, int a[], int k){
pair<int, int> arr[n];
for (int i = 0; i < n; i++){
arr[i].first = a[i];
arr[i].second = i;
}
sort(arr, arr + n);
int count = 1;
for (int i = 1; i < n; i++)
if (arr[i].first == arr[i - 1].first)
count++;
if (count < k){
cout << "-1";
return;
}
for (int i = 0; i < k - 1; i++){
indice(n, arr);
for (int j = 1; j < n; j++){
if (arr[j].first == arr[j - 1].first){
swap(arr[j], arr[j - 1]);
break;
}
}
}
indice(n, arr);
}
int main(){
int a[] ={2,5,6,2,2,2,2};
int n = sizeof(a) / sizeof(a[0]);
int k = 4;
permutation(n, a, k);
return 0;
} 출력
위의 프로그램을 실행하면 다음 출력이 생성됩니다.
0 3 4 5 6 1 2 3 0 4 5 6 1 2 0 3 4 5 6 1 2 3 0 4 5 6 1 2