Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม C

พิมพ์ k การเรียงสับเปลี่ยนการเรียงลำดับที่แตกต่างกันของอาร์เรย์ที่กำหนดในโปรแกรม C


จากอาร์เรย์ a[] ที่มีจำนวนเต็ม N ความท้าทายคือการพิมพ์การเรียงสับเปลี่ยนของดัชนี 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