In k hoán vị đã sắp xếp khác nhau của mảng trong C

Cho mảng a[] chứa N số nguyên, in k hoán vị chỉ số khác nhau sao cho giá trị tại các chỉ số đó tạo thành dãy không giảm. In -1 nếu không thể.

Ví dụ

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

Sắp xếp mảng và giữ chỉ số gốc -> hoán vị đầu tiên. Hoán đổi cặp phần tử bằng nhau liên tiếp để sinh hoán vị tiếp theo.

Thuật toán

BẮT ĐẦU
HÀM indice(n, pair array[])
    IN array[i].second
HÀM permutation(n, a[], k)
    TẠO pair arr[n] LƯU (giá trị, chỉ số)
    SẮP XẾP arr
    ĐẾM SỐ CẶP PHẦN TỬ BẰNG NHAU LIÊN TIẾP -> count
    NẾU count < k THÌ IN -1, TRẢ VỀ
    VỚI i=0 ĐẾN k-2
        GỌI indice(n, arr)
        TÌM CẶP arr[j].first == arr[j-1].first -> HOÁN ĐỔI, BREAK
    GỌI indice(n, arr)
KẾT THÚC

Chương trình C++ ví dụ

#include <bits/stdc++.h>
using namespace std;

void indice(int n, pair array[]) {
    for (int i = 0; i < n; i++) cout << array[i].second << " ";
    cout << endl;
}

void permutation(int n, int a[], int k) {
    pair 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;
}

Kết quả

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