Écrivez un code en C++ pour trouver le nombre de permutations avec K paires ordonnées inversement

Dans un tableau, si a[i] > a[j] et 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.

La méthode de solution

Nous pouvons utiliser la méthode de la force brute, trouver d'abord toutes les permutations des N premiers nombres, puis vérifier si toutes les inversions sont égales ou K. Si tel est le cas, incrémentez le compteur de résultats.

Méthode efficace

Dans cette méthode, nous avons N chiffres des N premiers nombres naturels. Toutes les permutations de ce nombre sont calculées ailleurs, à partir desquelles on retrouve K permutations. Pour le trouver, nous insérerons le nombre suivant Nième (maximum) dans toutes les permutations et après avoir ajouté ce nombre, nous chercherons les nombres dont le nombre d'inversions est égal à K qui devraient être comptés dans notre résultat. En prenant une permutation de (N – 1) nombres sans (K – 3) inversions, nous déplacerions le nouveau nombre au troisième index à partir du dernier index. Avec K nombre d'inversions, find_permutations(N-1, K-3) sera notre réponse. La même logique peut être utilisée pour d’autres inversions et nous obtiendrons la récursion ci-dessus comme réponse finale.

Input

#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;
}

Output

0

Input− N = 4, K = 3

Output− 6

Conclusion

Dans cet article, nous avons résolu un problème pour trouver un problème avec O(n * k) Permutation temporelle de K inversions de complexité. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!