[C]probleme permutation colonnes d'un tableau

Version imprimable

20/03/2008, 00h35
memo67

[C]probleme permutation colonnes d'un tableau
Bonsoir,

Voila j'suis nouveau et j'ai un petit soucis en C pour mon ter..
J'ai fais mon programme en maple et tout marche:
il y a une fonction qui s'appelle randperm qui fait:
b := randperm(18)
->b := [15, 10, 4, 8, 12, 5, 1, 11, 9, 2, 18, 13, 16, 17, 6, 7, 3, 14]
il affiche aleatoirement une permutation d'un vecteur ligne sans repetition des valeurs..

Mon probleme c'est qu'en C il n'y a pas de fonction similaire..;p

J'ai fais un test qui ressemble à ca:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 int main(){ int a,i; int tab[10]; for(i=0;i<10;i++){ a=rand()%11; tab[i]=a; printf("%d\n",tab[i]); } return 0; }
il ma'affiche par exemple->6,10,6,2,1,4,0,6,3,1

Le programme compile pas de probleme mais m'affiche un tableau avec des valeurs qui dans la plupart des cas sont egaux or c'est pas ce que je veux,je veux juste une permutation aleatoire.. :-(
J'ai essayé de faire des boucles while, for,..mais rien a faire..

Si quelqu'un pouvait m'aider, please.. merci d'avance..
20/03/2008, 01h05
Sve@r

Citation:

Envoyé par memo67

Bonsoir,

Voila j'suis nouveau et j'ai un petit soucis en C pour mon ter..
J'ai fais mon programme en maple et tout marche:
il y a une fonction qui s'appelle randperm qui fait:
b := randperm(18)
->b := [15, 10, 4, 8, 12, 5, 1, 11, 9, 2, 18, 13, 16, 17, 6, 7, 3, 14]
il affiche aleatoirement une permutation d'un vecteur ligne sans repetition des valeurs..

Mon probleme c'est qu'en C il n'y a pas de fonction similaire..;p

J'ai fais un test qui ressemble à ca:
int main(){

int a,i;
int tab[10];

for(i=0;i<10;i++){
a=rand()%11;
tab[i]=a;
printf("%d\n",tab[i]);
}
return 0;
}
il ma'affiche par exemple->6,10,6,2,1,4,0,6,3,1

Le programme compile pas de probleme mais m'affiche un tableau avec des valeurs qui dans la plupart des cas sont egaux or c'est pas ce que je veux,je veux juste une permutation aleatoire.. :-(
J'ai essayé de faire des boucles while, for,..mais rien a faire..

Si quelqu'un pouvait m'aider, please.. merci d'avance..

Il y a plusieurs façons de faire ça. La plus simple, c'est que lorsque tu choisis la valeur qui ira dans la case "n", tu balayes ton tableau de 0 à "n - 1" et tu regardes si la valeur en question n'y est pas déjà. Une méthode plus rapide est de travailler avec 2 tableaux. Le second tableau ne contient que 0 ou 1 et il commence complètement à 0. Puis lorsque tu tires un nombre (par exemple le 7) ben tu mets 1 dans l'élément [7] de ce tableau. Ensuite, si tu retires le 7 ben tu refuses ce chiffre car l'élément [7] est déjà à 1...

Sinon concernant ton code j'ai plusieurs remarques
- la variable "a" ne sert à rien
- il te faut initialiser le générateur aléatoire car sinon tu auras toujours la même séquence => voir à ce sujet la fonction srand() => tu peux par exemple utiliser l'instruction srand(time(NULL)) voire même srand(time(NULL) ^ getpid()) si t'es sur un Unix
- tu génères un nombre par random et tu lui appliques un modulo 11 => cette méthode est assez décriée car elle n'offre pas un étalement suffisant dans le choix possible des nombres aléatoires. En général, on préfère utiliser la formule suivante :
rand() * 11 / (RAND_MAX + 1.0)

Salut et bienvenue sur Developpez.com :)

Pour obtenir des valeurs aléatoires, il faut lancer le générateur de nombres pseudo-aléatoires avant d'utiliser rand().

Ton nouveau code sera donc :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include<stdio.h> #include<time.h> int main() { int a,i; int tab[10]; srand(time(NULL)); for(i= 0; i < 10; i++) { a=rand()%11; tab[i]= a; printf("%d\n",tab[i]); } return 0; }
@++ :)

Citation:
Envoyé par buchs
Salut et bienvenue sur Developpez.com :)

Pour obtenir des valeurs aléatoires, il faut lancer le générateur de nombres pseudo-aléatoires avant d'utiliser rand().

Ton nouveau code sera donc :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include<stdio.h> #include<time.h> int main() { int a,i; int tab[10]; srand(time(NULL)); for(i= 0; i < 10; i++) { a=rand()%11; tab[i]= a; printf("%d\n",tab[i]); } return 0; }
@++ :)
Oui mais t'as pas tout lu dans son problème - Il veut des chiffres tous différents...
Et la variable "a" est toujours inutile...

Pour obtenir une permutation aléatoire de ton tableau, tu peux par exemple utiliser la fonction shuffle ci-dessous:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define ARRAY_SIZE(arr) ( sizeof (arr) / sizeof *(arr) )
 
/* -tc- Voir: http://c.developpez.com/faq/?page=nombres#NOMBRES_random_bornes */
int alea(int n)
{
   int partSize   = (n == RAND_MAX) ? 1 : 1 + (RAND_MAX - n)/(n+1);
   int maxUsefull = partSize * n + (partSize-1);
   int draw;
 
   do
   {
      draw = rand();
   } while (draw > maxUsefull);
   return draw/partSize;
}
 
/* -tc- Utilise l'algorithme de Fisher & Yates */
int shuffle(int *a, size_t size_a)
{
    int err = 0;
 
    if (a != NULL && size_a > 1)
    {
        size_t n = size_a;
 
        while (--n > 0)
        {
            /* -tc- k est un entier aleatoire entre 0 et n */
            size_t k = alea(n);
 
            if (k != n)
            {
                /* -tc- On echange le k-eme et le n-eme element */
                int tmp = a[n];
                a[n] = a[k];
                a[k] = tmp;
            }
        }
    }
    else
    {
        /* Erreur: argument invalide */
        err = 1;
    }
    return err;
}
 
/* -tc- Dans ce programme, on desire afficher aleatoirement 5 nombres parmi
   l'ensemble {0,1,2,3,4,5,6,7,8,9} sans repetition */
int main(void)
{
    int nombres[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    size_t n = 5;
    size_t i;
 
    srand(time(NULL));
    shuffle(nombres, ARRAY_SIZE(nombres));
 
    for (i = 0; i < ARRAY_SIZE(nombres) && i < n; i++)
    {
        printf("%d ", nombres[i]);
    }
    printf("\n");
 
    return 0;
}

Thierry

Bonjour,

c'est un type de permutation classique que l'on résoud de la façon suivante :
- On place les nombres dans l'ordre dans le tableau.
- On fait N permutations.
Code:

1 2 3 4 5 6 7 8 9 10 11 void MaPermutation(int Tab[], int n) { int i, j ; for (i=0 ; i < n ; i++) Tab[i] = i ; // On met tous les nombres une fois. for (i=0 ; i < n ; i++) // On fait N tirages { j = rand()%n ; Permuter(&Tab[i], &Tab[j]) ; // On permute pour rendre le tableau aléatoire. } }
PS : merci d'utiliser :tagcode: