C প্রোগ্রামে অ্যারের kটি ভিন্ন সর্টেড পারমিউটেশন প্রিন্ট করা

ভূমিকা

একটি অ্যারে দেওয়া থাকলে, তার kটি ভিন্ন পারমিউটেশন প্রিন্ট করতে হবে যাতে প্রতিটি পারমিউটেশনে উপাদানগুলো নন-ডিক্রিজিং অর্ডারে (non-decreasing order) থাকে। অ্যারেতে ডুপ্লিকেট মান থাকলে সে কারনে একাধিক ভ্যালিড পারমিউটেশন সম্ভব।

উদাহরণ

ইনপুট: arr[] = {2,5,6,2,2,2,2}, k = 4
আউটপুট:
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

এলগরিদম

void permutation(int n, int a[], int k)
শুরু
  pair arr[n] // {value, original_index}
  সর্ট করুন arr কে value অনুযায়ী
  count = 1
  i = 1 থেকে n-1: যদি arr[i].first == arr[i-1].first হয়: count++
  যদি count < k: -1 প্রিন্ট করে রিটার্ন
  i = 0 থেকে k-2:
    বর্তমান পারমিউটেশনের ইন্ডেক্স প্রিন্ট করুন
    j = 1 থেকে n-1: যদি arr[j].first == arr[j-1].first হয়:
      swap(arr[j], arr[j-1]), ব্রেক
  শেষ পারমিউটেশন প্রিন্ট করুন
শেষ

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;

void printIndices(int n, pair arr[]) {
    for (int i = 0; i < n; i++) cout << arr[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++) {
        printIndices(n, arr);
        for (int j = 1; j < n; j++) {
            if (arr[j].first == arr[j-1].first) {
                swap(arr[j], arr[j-1]);
                break;
            }
        }
    }
    printIndices(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