在C程序中打印给定数组的k个不同排序的排列。
给定一个包含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
对给定的数组进行排序,并跟踪每个元素的原始索引。这给出了一个必需的排列。现在,如果任意两个连续元素相等,则可以交换它们以获得另一个排列。类似地,可以生成第三排列。
算法
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