Comptabiliser des permutations en C++ Résolu

Question

Bonjour,

Voici un nouveau post plus clair j'éspère. Je cherche à ce qu'un programme en C++ (celui copié en fin de poste par exemple) en plus de faire défiler toutes les permutations d'un ensemble de chiffre, les comptabilisent. Et qu'il m'affiche à la fin 40,320 permutations (pour les cas à 8 chiffres).

Ensuite je cherche des variantes qui consistent à ne comptabiliser que certaines d'entre elles. Par exemple celles qui sont telles que le premier élément est plus grand que le cinquième, le second que le sixième,... le quatrième que le huitième.

Le programme ci-dessous fonctionne pour faire défiler les permutations mais je ne sais comment les comptabiliser.

Merci d'avance pour votre aide

kjones

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <stdlib.h>

/**
Read a number, N, from standard input and print the
permutations.
*/

void print(const int *v, const int size)
{
if (v != 0) {
for (int i = 0; i < size; i++)

{
printf("%4d", v[i] );

}

printf("\n");

} }// print

void swap(int *v, const int i, const int j)
{
int t;
t = v[i];
v[i] = v[j];
v[j] = t;
}

void rotateLeft(int *v, const int start, const int n)
{
int tmp = v[start];
for (int i = start; i < n-1; i++) {
v[i] = v[i+1];
}
v[n-1] = tmp;
} // rotateLeft

void permute(int *v, const int start, const int n)
{

print(v, n);

if (start < n) {
int i, j;
for (i = n-2; i >= start; i--) {
for (j = i + 1; j < n; j++) {
swap(v, i, j);
permute(v, i+1, n);
} // for j
rotateLeft(v, i, n);
} // for i
}
} // permute

void init(int *v, int N)
{
for (int i = 0; i < N; i++) {
v[i] = i+1;
}
} // init

void
main()
{
char buf[80];
int N;
printf("Enter the number of elements: ");
fgets(buf, sizeof(buf), stdin );
sscanf(buf, "%d", &N);

if (N > 0 && N <= 10) {
int *v = new int[N];
init(v, N);
permute(v, 0, N);
delete [] v;
}
}

Configuration: Windows XP
Firefox 2.0.0.4

mamiemando · Answer

La manière la plus simple de programmer ça c'est d'écrire un appel récursif qui va parcourir l'arbre de recherche correspondant à l'ensemble des permutations. L'appel récursif doit passer à ses fils
- la profondeur à laquelle il est rendu (par exemple 3 si j'ai déjà tiré les trois premiers chiffres)
- la profondeur max (par exemple 8 dans le cas des 8 chiffres)
- les chiffres tirés jusqu'ici (par exemple stocké dans un std::vector<short>)

Dans le cas ou les permutations doivent vérifier certaines propriétés, il est possible de définir des coupes qui éviteront de poursuivre l'appel récursif vers des feuilles qui ne serviront de toute façon à rien.

Je ne suis pas sûre d'avoir compris ce que tu comptais mais si ce sont tous les nombres de K chiffres, où chaque chiffre est distinct et prend une valeur comprise entre 0 et 9 ça donne ce genre de chose (ici K=3)

#include <vector>
#include <iostream>
#include <cassert>

void f(
    unsigned prof,              // la profondeur courante (nombre de chiffre choisis)
    const unsigned & prof_max,  // la profondeur max (nombre de chiffre à choisir)
    std::vector<short> perm,    // la permutation courante
    std::vector<bool> marked,   // les nombres utilisés
    unsigned & compteur         // le nombre de permutations rencontrées
){
    if (prof < prof_max){
        for(unsigned i=0;i<=9;++i){
            if (marked[i]) continue;
            std::vector<short> perm_suivant = perm;
            perm_suivant.push_back(i);
            std::vector<bool> marked_suivant = marked;
            marked_suivant[i] = true;
            f(prof+1,prof_max,perm_suivant,marked_suivant,compteur);
        }
    }else{ // le nombre a la taille voulue
        for(unsigned i=0;i<perm.size();++i) std::cout << perm[i];
        std::cout << std::endl;
        ++compteur;
    }
}

void perm(const unsigned & prof_max){
    assert(prof_max<=10);
    std::vector<short> perm0;
    std::vector<bool> marked0(10,false);
    unsigned compteur = 0; // partagé par tous les appels recursifs
    f(0,prof_max,perm0,marked0,compteur);
    std::cout << "compteur = " << compteur << std::endl;
}

int main(){
    perm(3);
    return 0;
}

Ce qui donne

(mando@aldur) (~) $ ./a.out
012
013
014
015
016
017
018
019
021
023
024
025
...
975
976
978
980
981
982
983
984
985
986
987
compteur = 720

Tu as donc bien toutes les permutations de taille 3 d'un ensemble à 10 éléments (valeurs de 0 à 9). C'est ce que tu voulais ?

Bonne chance

mamiemando · Answer

Oui mais ouvre un nouveau sujet en faisant référence à celui-ci pour maintenir la clarté de ce fil de discussion.

mamiemando · Answer

Parfait je vais y jeter un oeil tout à l'heure

Comptabiliser des permutations en C++

3 réponses

Discussions similaires

Newsletters