Schreiben Sie mit C++ einen Code, um die Anzahl der Permutationen mit K umgekehrt geordneten Paaren zu ermitteln

Wenn in einem Array a[i] > a[j] und i

Input: N = 4, K = 1
Output: 3
Explanation: Permutation of the first N numbers in total : 1234, 1243, 1324 and 2134. With 1 inversion we have 1243, 1324 and 2134.

Input : N = 3, K = 2
Output : 3
Explanation: Permutation of the first N numbers in total : 123, 132, 213, 231, 312, and 321 with 2 inversions we have 231, 312 and 321.

Die Lösungsmethode

Wir können die Brute-Force-Methode verwenden, zuerst alle Permutationen der ersten N Zahlen finden und dann prüfen, ob alle Umkehrungen gleich oder K sind. Wenn ja, erhöhen Sie den Ergebniszähler.

Effiziente Methode

Bei dieser Methode haben wir N Ziffern der ersten N natürlichen Zahlen. Alle Permutationen dieser Zahl werden an anderer Stelle berechnet, woraus wir K Permutationen finden. Um es zu finden, fügen wir die nächste Zahl N-th (Maximum) in alle Permutationen ein und suchen nach dem Hinzufügen dieser Zahl nach Zahlen, deren Inversionsanzahl gleich K ist und in unserem Ergebnis gezählt werden soll. Bei einer Permutation von (N – 1) Zahlen ohne (K – 3) Inversionen würden wir die neue Zahl am dritten Index vom letzten Index verschieben. Bei K Umkehrungen ist find_permutations(N-1, K-3) unsere Antwort. Die gleiche Logik kann für andere Inversionen verwendet werden und wir erhalten die obige Rekursion als endgültige Antwort.

Eingabe

#include <bits/stdc++.h>
using namespace std;
const int X = 100;
int a = 0;
int arr[X][X];
// recursive function
int find_permutations (int N_numbers, int K_inversion){
    if (N_numbers == 0){
      return 0;            // return 0 when N becomes 0
    }
    if (K_inversion == 0)
        return 1;            // return 1 when K becomes 1
    if (arr[N_numbers][K_inversion] != 0)
        return arr[N_numbers][K_inversion];
    int result = 0;
    for (int i = 0; i <= K_inversion; i++){

        if (i <= N_numbers - 1)
          result += find_permutations (N_numbers - 1, K_inversion - i);
    }
    arr[N_numbers][K_inversion] = result;
    return result;
}
// main function
int main (){
    int N, K;
    cin >> N;    // taking input from user
    cin >> K;
    cout << find_permutations (N, K);
    return 0;
}

Ausgabe

0

Eingabe− N = 4, K = 3

Ausgabe− 6

Schlussfolgerung

In diesem Artikel haben wir ein Problem gelöst, um ein Problem mit O(n * k) zu finden Zeitpermutation von K Komplexitätsinversionen. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, dieser Artikel ist hilfreich für Sie.

Das obige ist der detaillierte Inhalt vonSchreiben Sie mit C++ einen Code, um die Anzahl der Permutationen mit K umgekehrt geordneten Paaren zu ermitteln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!