Bonjour,

J'essaye de faire cet exercice mais je n'ai pas compris la question 2, je ne sais pas comment faire. Ni ce que c'est un tableau d'inversion (question 1) et les questions 5 et 6.

Enoncé:

Un tableau de n entiers est une permutation s'il contient des entiers 0,1,...,n-2,n-1 dans un ordre quelconque.

Par exemple, 2 0 3 1  a une inversion en (0,1), une autre en (0,3) et une dernière (2,3) soit 3 inversions en tout.

Si tab est une permutation de longueur n, son tableau d'inversions est le tableau d'entiers de longueur n dont l'élément d'indice i contient le nombre d'inversions en (i, j) de tab pour i+1<= k <= n-1

Par exemple, le tableau d'inversion 2 0 3 1 est 2 0 1 0

Questions:

1. Donner le nombre total d'inversion de la permutation 3 1 2 0 et son tableau d'inversions

2. Ecrire une fonction maxInversions qui prend en argument un entier n et renvoie la permutation de longueur n qui a le plus grand nombre d'inversions, parmi toutes les permutations de longueur n

3. Ecrire ne fonction nbInversions qui prend en argument un tableau tab d'entiers et renvoie le nombre d'inversions de tab si tab est une permutation et -1 sinon

4. Ecrire une fonction tableauInversions qui prend en argument un tableau tab d'entiers et renvoie le tableau d'inversions de tab si tab est une permutation et null sinon

5. Ecrire une fonction estInv qui prend en argument un tableau d'entiers et teste si c'est le tableau d'inversions d'une permutation 

6. Ecrire une fonction inv2Perm qui prend en argument un tableau tab d'entiers et renvoie la permutation est tab est le tableau d'inversions si tab est le tableau d'inversions d'une permutation et null sinon

Ce que j'ai fais

/*Question 1:
Le tableau [3|1|2|0] a donc 5 inversions, car
- il y a 3 nombres à gauche du 3 qui sont inférieurs à 3 (1, 2, 3)
- 1 nombre à droite du 1 qui est inférieur à 1 (0)
-1 nombre à droite du 2 qui est inférieur à 2 (0). 
-Il n’y a pas de nombre à droite du 0.

Ici je n'ai pas compris le tableau inverse
*/

/* question 3
D’après l’énoncé, une inversion est un couple d’indice pour lesquels les entiers correspondants dans le tableau sont en ordre décroissant, c’est-à-dire que l’entier à gauche est plus grand que celui à droite.*/

static int nbInversions(int[] tab) {
    // si tab n’est pas une permutation
    if (!estPerm(tab)){
       return -1;
    }
    int nb = 0;

    // pour chaque entier du tableau...
    for (int i=0; i<tab.length; i++) {

        // ... on regarde chaque entier à droite
        for (int j=i+1; j<tab.length; j++) {

            // si il y en a un plus petit
            // on incrémente le nombre d’inversions
            if (tab[j] < tab[i]){
               nb++;
            }
        }
    }

    return nb;
}
//question 4

static int[] tableauInversions(int[] tab) {

    int[] inv = new int[tab.length];

    // pour chaque entier du tableau
    for (int i=0; i<tab.length; i++) {

        // on compte le nombre d'inversions entre cet entier et les entiers
        // à sa droite
        int nb = 0;

        for (int j=i+1; j<tab.length; j++) {
            if (tab[j] < tab[i]) nb++;
        }

        // on stocke ce nombre dans le tableau d’inversions
        inv[i] = nb;

    }

    return inv;
}

Merci d'avance et bonne journée

Salut,

J'ai pas tout saisi mais bon je vais essayer

1/ Le tableau d'inversion est simplement le nombre d'inversion a chaque indice de ton tableau de base. Donc pour 3120, ca donne 3110 (3 inversion pour 3 - 1 pour 1 - 1 pour 2 - 1 pour 0)

2/ Euh la je pense qu'il doit y avoir un tableau quelque part ...

5/aucune idee

6/ renvois l’énoncé stp il y a des fautes

merci pour ta réponse

pour la question 2 un tableau de quoi ?

Pour la question 1 pourquoi c'est 3110 et pourquoi tu fais 3-1... 1-1...

la question 6 oui j'ai mal tapé:

Ecrire une fonction inv2Perm qui prend en argument un tableau tab d'entiers et renvoie la permutation dont tab est le tableau d'inversions si tab est le tableau d'inversions d'une permutation et null sinon.

2/ Un tableau d'entier qui serait un tableau de permutation (je pense.. ca me perd pas mal ton exo )

1/ tableau 3120.

'3' a (3) permutations

1 a (1) permutation

2 a (1) permutation

0 a (0) permutation

Ce qui donne comme tableau d'inversion : 3110

6/ Ça y est je suis perdu x)

ah ok mdr je comprends mieux. L'essentiel j'ai compris le truc de permutation.