Bonjour,

J'ai un tableau d'entiers (de 0 à N), initialement dans l'ordre
numérique :

tableau[0] =0
tableau[1] =1
tableau[2] =2
....
tableau[N] =N

Je recherche un algorithme qui mélange le tableau de façon aléatoire,
c'est à dire qu'il contienne toujours les mêmes valeurs (les entiers de
0 à N), mais dans un ordre aléatoire.

Exemple de résultat recherché :

tableau[0] =22
tableau[1] =2
tableau[2] =11
....
etc.

Merci de vos suggestions.

Le Sun, 07 Mar 2010 19:09:03 +0100
ByB a écrit
[..]
>
>Exemple de résultat recherché :
>
>tableau[0] =22
>tableau[1] =2
>tableau[2] =11
>...
>etc.
>
>Merci de vos suggestions.

Utilise le Fisher-Yate shuffle.

// i = size - 1 = (N+1)-1 = N , ici le tableau a N+1 éléments
for(i=N; i>0; i--)
{
j = random(0,i); // retourne un nombre 0 <= j <= i
echanger( tableau[i] , tableau[j] );
}

Le 07/03/2010 21:34, zwim répondait à ByB :
>>
>>Je recherche un algorithme qui mélange le tableau de façon aléatoire,
>
> Utilise le Fisher-Yate shuffle.

Et avant de l'implémenter toi-même, vérifie qu'il n'est pas déjà proposé
en standard. Par exemple, en PHP, tu peux utiliser la fonction shuffle.

Olivier Miakinen a formulé la demande :
> Le 07/03/2010 21:34, zwim répondait à ByB :
>>>
>>> Je recherche un algorithme qui mélange le tableau de façon aléatoire,
>>
>> Utilise le Fisher-Yate shuffle.
>
> Et avant de l'implémenter toi-même, vérifie qu'il n'est pas déjà proposé
> en standard. Par exemple, en PHP, tu peux utiliser la fonction shuffle.

Je travaille en C# (avec Microsoft .NET).

On Mon, 08 Mar 2010 11:32:08 +0100, ByB <no_mail@no_mail.invalid>:

>> Et avant de l'implémenter toi-même, vérifie qu'il n'est pas déjà proposé
>> en standard. Par exemple, en PHP, tu peux utiliser la fonction shuffle.
>
>Je travaille en C# (avec Microsoft .NET).

Jamais utilisé, mais .NET est un framework énorme. Ça m'étonnerait
beaucoup que tu n'y trouves pas des implémentations de tous ces
algorithmes de base.

Bonjour,

Le 08/03/2010 11:32, ByB m'a répondu :
>>>
>>> Utilise le Fisher-Yate[s] shuffle.
>>
>> Et avant de l'implémenter toi-même, vérifie qu'il n'est pas déjà proposé
>> en standard. Par exemple, en PHP, tu peux utiliser la fonction shuffle.
>
> Je travaille en C# (avec Microsoft .NET).

Je n'y connais rien, alors tu devras toi-même regarder ici :
http://www.google.fr/search?q="dot+net"+"fisher+yates"

Cela dit, le premier lien semble prometteur :
http://dotnetperls.com/shuffle-array

Cordialement,

ByB a écrit :
> Je recherche un algorithme qui mélange le tableau de façon aléatoire,
> c'est à dire qu'il contienne toujours les mêmes valeurs (les entiers de
> 0 à N), mais dans un ordre aléatoire.

Le plus simple est de prendre une fonction de tri dans
laquelle on remplace la fonction de comparaison par
une fonction aléatoire.

La plupart des fonctions de tri prennent en paramètre
la fonction de comparaison: le tri aléatoire prend alors
à peine une ligne de code.

Bonjour,

Le 09/03/2010 19:24, Joe Cool a écrit :
>
>> Je recherche un algorithme qui mélange le tableau de façon aléatoire,
>> c'est à dire qu'il contienne toujours les mêmes valeurs (les entiers de
>> 0 à N), mais dans un ordre aléatoire.
>
> Le plus simple est de prendre une fonction de tri dans
> laquelle on remplace la fonction de comparaison par
> une fonction aléatoire.

Troll mis à part, quelle est la qualité du hasard obtenu par cette
méthode ? Je suppose que cela dépend de l'algorithme de tri lui-même,
non ?

On Tue, 09 Mar 2010 19:24:09 +0100, Joe Cool <zierouhli>:

>Le plus simple est de prendre une fonction de tri dans
>laquelle on remplace la fonction de comparaison par
>une fonction aléatoire.

Non, ça ne fonctionne pas correctement.

On Tue, 09 Mar 2010 19:24:09 +0100, Joe Cool <zierouhli>:

>Le plus simple est de prendre une fonction de tri dans
>laquelle on remplace la fonction de comparaison par
>une fonction aléatoire.

Cherche "well-known trap" sur
http://www.robweir.com/blog/2010/02/...er-ballot.html

Le 10/03/2010 00:40, Fabien LE LEZ répondait à Joe Cool :
>
>>Le plus simple est de prendre une fonction de tri dans
>>laquelle on remplace la fonction de comparaison par
>>une fonction aléatoire.
>
> Cherche "well-known trap" sur
> [..]

Merci, c'est bien ce que je pensais. Note que je soupçonne Joe Cool
d'avoir déjà su que ça ne marchait pas avant de le proposer... ce ne
serait pas son premier troll, ni probablement son dernier ! ;-)

Olivier Miakinen a écrit :
> Le 09/03/2010 19:24, Joe Cool a écrit :
>> Le plus simple est de prendre une fonction de tri dans
>> laquelle on remplace la fonction de comparaison par
>> une fonction aléatoire.
>
> Troll mis à part, quelle est la qualité du hasard obtenu par cette
> méthode ? Je suppose que cela dépend de l'algorithme de tri lui-même,
> non ?

Le but est de générer simplement une permutation aléatoire des N premiers
entiers suivant une distribution uniforme.

Il faut évidemment que l'algorithme de tri soit optimal, c'est-à-dire
qu'il compare au plus une fois les membres de chaque sous-ensembles à
deux éléments. On considère une précision de l'ordre de 1/log(N!)^2: plus
le tableau est grand, mieux ça marche.

La première conséquence est que le module du tri pour la comparaison
aléatoire induit un ordre total sur les données; c'est le cas dans le
tri fusion, ce n'est pas le cas dans le tri à bulles.

La seconde conséquence est que les permutations sont uniformément réparties.
En effet, en considérant l'arbre itf des comparaisons effectuées dans l'algorithme,
le module du tri pour la fonction de comparaison correspond à un chemin enraciné
unique dans cet arbre. Comme les modules sont équiprobables, chaque exécution
correspond à un choix uniforme d'un chemin, donc d'une permutation.

En résumé, il y a trois conditions à remplir:
- la fonction de comparaison est aléatoire;
- la précision est supérieure aux tolérances;
- la fonction de tri est optimale.

C'est la dernière condition qui fait échouer la méthode quand les algos de
tri sont programmés par des foireux. J'ai supposé que je n'avais pas
affaire à des foireux. Ai-je eu tort?

Fabien LE LEZ a écrit :
> Cherche "well-known trap" sur
> [..]

Le type fait un test statistique sorti du chapeau sur un algo aléatoire.
De quoi parle-t-il au juste? De la qualité de sa fonction random, de sa
fonction de tri, de son compilateur ou de son test statistique? Aucune preuve,
rien de consistant, rien de rigoureux, juste du brassage de vent.

Le Sat, 13 Mar 2010 16:15:41 +0100
Joe Cool a écrit
>Olivier Miakinen a écrit :
>
>Le but est de générer simplement une permutation aléatoire des N premiers
>entiers suivant une distribution uniforme.
>
>Il faut évidemment que l'algorithme de tri soit optimal, c'est-à-dire
>qu'il compare au plus une fois les membres de chaque sous-ensembles à
>deux éléments. On considère une précision de l'ordre de 1/log(N!)^2: plus
>le tableau est grand, mieux ça marche.
>
>La première conséquence est que le module du tri pour la comparaison
>aléatoire induit un ordre total sur les données; c'est le cas dans le
>tri fusion, ce n'est pas le cas dans le tri à bulles.

Non le tri-fusion compare plusieurs fois deux éléments donnés, une
fois à la création de la sous-liste et éventuellement une fois de plus
lors de la fusion.

Les deux paragraphes ci-dessus sont contradictoires.

>La seconde conséquence est que les permutations sont uniformément réparties.
>En effet, en considérant l'arbre itf des comparaisons effectuées dans l'algorithme,
>le module du tri pour la fonction de comparaison correspond à un chemin enraciné
>unique dans cet arbre. Comme les modules sont équiprobables, chaque exécution
>correspond à un choix uniforme d'un chemin, donc d'une permutation.
>
>En résumé, il y a trois conditions à remplir:
>- la fonction de comparaison est aléatoire;
>- la précision est supérieure aux tolérances;
>- la fonction de tri est optimale.
>
>C'est la dernière condition qui fait échouer la méthode quand les algos de
>tri sont programmés par des foireux. J'ai supposé que je n'avais pas
>affaire à des foireux. Ai-je eu tort?

Le tri par insertion respecte toutes les conditions que tu dis et il
conduit à un mélange totalement biaisé.

$ ./tri_biais.exe
0 : 17.4152
1 : 17.3739
2 : 16.7359
3 : 15.8884
4 : 14.8902
5 : 13.9714
6 : 12.9833
7 : 12.0225
8 : 10.9833
9 : 10.0123
10 : 8.9921
11 : 7.975
12 : 7.0711
13 : 6.0998
14 : 5.0615
15 : 4.1495
16 : 3.3153
17 : 2.4219
18 : 1.6258
19 : 1.0116

Voici un test répété 10 000 fois d'un tri aléatoire par insertion en
remplaçant la fonction de comparaison par une fonction aléatoire.

Les résultats présentent la moyenne des places des éléments, c'est
totalement biaisé, normalement tout le monde devrait être autour de
N/2 = 10.

Voici le code :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 20
#define NBTESTS 10000

/* -------------------------------------- */
typedef struct _liste_t
{
int val;
struct _liste_t *next;

} liste_t;


void push(liste_t *L, int x)
{
liste_t *tmp;

if(!L) return;

tmp = malloc(sizeof * tmp);
tmp->val = x;
tmp->next = NULL;

tmp->next = L->next;
L->next = tmp;

return;
}

void detruit(liste_t *L)
{
liste_t * tmp;

while(L)
{
tmp = L->next;
free(L);
L = tmp;
}
}

/* -------------------------------------- */
int superieur(int a, int b)
{
//return (a>b);
return rand() > (RAND_MAX/2);
}

/* -------------------------------------- */
int main(void)
{
int i,k,S[N];
liste_t L;
liste_t *tmp;

for(k=0; k<N; k++) S[k] = 0;

srand((unsigned)time(NULL));

//Statistiques
for(k=0; k<NBTESTS; k++)
{
//Tri par insertion
L.val = -1;
L.next = NULL;

for(i=0; i<N; i++)
{
tmp = &L;

while(tmp->next)
{
if(superieur(i,tmp->val))
tmp=tmp->next;
else
break;
}

push(tmp,i);
}

//Comptage
tmp = L.next;
i=0;

while(tmp)
{
//printf("%d ",tmp->val);
S[tmp->val] += i;

tmp = tmp->next;
i++;
}

detruit(L.next);
}

//Resultats
for(i=0; i<N; i++)
printf("%2d : %g\n",i,(double)S[i]/NBTESTS);

return 0;
}

Bref le foireux dans l'histoire c'est toi.

zwim a écrit :
> Non le tri-fusion compare plusieurs fois deux éléments donnés, une
> fois à la création de la sous-liste et éventuellement une fois de plus
> lors de la fusion.

La création de sous-listes ne fait pas intervenir le contenu des listes,
seulement leur taille. De plus, cette phase est facultative dans la version
itérative du tri fusion.

> Le tri par insertion respecte toutes les conditions que tu dis et il
> conduit à un mélange totalement biaisé.

Le tri par insertion n'est pas optimal puisque sa complexité dans le pire
des cas est en O(N^2) pour un tableau de taille N.

Encore raté. Vous repasserez.