Permutation

[MacManus]

Bonjour.

J'utilise le C++

J'aimerais savoir comment programmer "une permutation (aléatoire) d'un ensemble fini de n points d'un plan".

Quelqu'un aurait-il une idée ?
merci beaucoup

[gigamesh]

bonjour,
dans une liste tu mets 1 2 3 4 ...n
Puis tu tires un nombre aléatoire entre 1 et la longueur de la liste,
tu extrait l'élément considéré et tu le places dans une deuxième liste ;
tu supprimes l'élément considéré de la première liste.

Tu recommences en plaçant le terme choisi en fin de liste 2...

bon c'est plutôt du LISP en fait ; tout dépend si tu as en C++ une structure de données qui permet de supprimer un élément d'une liste en "compactant" le reste de la liste.

Bah au pire, une fois que tu as choisi un élément de la liste initiale, tu le remplaces par zéro ; et au lieu de "le kième élément" tu écris "le kième élément non nul".

C'est sur que la complexité apparente de l'algorithme augmente, mais pas forcément sa complexité réelle, tout dépend de l'implémentation de "supprimer un élément dans une liste".

Sinon tu peux utiliser des listes chaînées... ou du Python.

[Ben314]

Salut,
On peut aussi s'en sortir avec un seul tableau T[1..n] que l'on initialise avec T[i]=i puis, pour i de n à 2 (en décroissant), on échange T[i] avec T[aléatoire de 1 à i].
On obtient ainsi un générateur aléatoire de permutations.

[fatal_error]

salut,

pour compléter légèrement.
Un point du plan est repéré par ses cordo (x,y).
Avec n points, on peut lui associer un identifiant.
Le premier point a l'ID 1, le second l'ID 2, etc...

Il suffit d'avoir un tableau qui associe a un ID ses coordonnées.
Ensuite, on permute (comme dit précédemment) sur l'ID des points.

A savoir, si tu as 1,2,3->2,1,3, ca veut dire que le point 2 a pris la place du point 1.

Ensuite, de manière plus pisseur de code, faudra que tu fasses gaffe aux generations aléatoires de rand (si tu utilises rand bien sûr) qui donne pas un truc exactement uniforme, mais bon, c'est un détail jpense

rq : joli avatar Ben :arme:

[MacManus]

(0 Killed) merci pour vos réponses!

j'essaye de suivre vos méthodes, Ben314 et fatal_error . En particulier, je tente d'écrire ce que me dit "fatal" pour ensuite générer des permutations selon "Ben"

1/ j'ai d'abord crée un tableau de vecteurs : coordonnees
2/ je le remplie au fur et à mesure avec une boucle for

voila ce que ca donne :


std::vector < std::vector > coordonnees;
coordonnees.resize(10000);

for(unsigned int i=3; i < m_vertices.size(); i++)
{
float x = m_vertices[i]->m_position.x ;
float y = m_vertices[i]->m_position.y ;
coordonnees[i].push_back(glm::vec2(x,y));
}

Bon biensûr, sans contexte, c'est pas très parlant...avec l'utilisation de certaines librairies, des pointeurs, bref...

mais je ne vois pas trop comment faire des permutations à présent...
Ben, est-ce qu'à ton avis je peux appliquer ce que tu dis avec mon unique tableau de vecteurs : coordonnees ??

merci bcp

ps : je pars bien de i=3 dans mon probleme...

[Ben314]

Oui, tu peut parfaitement utiliser l'algo directement sur ton tableau de vecteur. En fait, l'algo correspond trés précisément à "mélanger" les vecteurs comme on mélangerais un jeu de carte.
Là ou il faut un peu de théorie, c'est sur la façon de mélanger pour que tout tes résultats possible ait la même chance d'apparaitre.

Ici, pour mélanger "uniformément" tu fait une boucle

pour i=m_vertices.size() à i=4 (en descedant)
{ tirer k au hasard dans {3..i};
échanger les éléments i et k
}

Ce que suggére Fatal_Error est d'utiliser un deuxième tableau de "mélange" des indices qui évite de déplacer les coordonnées (c'est souvent malin si on a des "grosses" structures que l'on veut éviter de déplacer ou lorsque l'on veut garder la trace de l'ordre initial de la structure sans la recopier) :
Tu fabrique un tableau melang[3..nb_élément] d'entiers que tu initialise à mélang[i]=i puis tu le mélange.
Lorsque tu veut accéder à ton tableau coord[...] de départ "mélangé", tu utilise coord[mélang[i]]

[MacManus]

D'accord je comprends bien le problème, c'est parti !
Merci, c'est m'aider dans une des étapes de mon algo qui me réserve encore bien des surprises...