Générer arrangement aléatoire avec Maple

[ca34]

Bonjour.
Dans Maple (12), j'ai trouvé de quoi générer des permutations aléatoires de l'intervalle d'entiers [1..n] avec randperm ou de quoi générer des combinaisons aléatoires de l'intervalle d'entiers [1..n] avec randcomb.
Mais j'aimerais générer des arrangements aléatoires (en tenant compte de l'ordre). Par exemple, pour créer un arrangement de 2 éléments parmi [1..5], tout ce que j'ai trouvé, c'est générer une permutation et prendre les 2 premiers éléments:
[op(1 .. 2, randperm(5))]
ou générer une combinaison puis prendre une permutation:
randperm([op(randcomb(5, 2))])

Mais comme je fais des simulations avec des millions de tests, je trouve que ces deux solutions sont beaucoup moins efficaces que de générer directement un arrangement. Comment fait-on avec Maple ? Merci.

[geegee]

Bonjour.
Dans Maple (12), j'ai trouvé de quoi générer des permutations aléatoires de l'intervalle d'entiers [1..n] avec randperm ou de quoi générer des combinaisons aléatoires de l'intervalle d'entiers [1..n] avec randcomb.
Mais j'aimerais générer des arrangements aléatoires (en tenant compte de l'ordre). Par exemple, pour créer un arrangement de 2 éléments parmi [1..5], tout ce que j'ai trouvé, c'est générer une permutation et prendre les 2 premiers éléments:
[op(1 .. 2, randperm(5))]
ou générer une combinaison puis prendre une permutation:
randperm([op(randcomb(5, 2))])

Mais comme je fais des simulations avec des millions de tests, je trouve que ces deux solutions sont beaucoup moins efficaces que de générer directement un arrangement. Comment fait-on avec Maple ? Merci.

Bonjour,

boucle for
rand(6)rand(6)

[ca34]

Bonjour.
Je ne pense pas que cette méthode marche dans mon cas car ce sont des arrangements sans répétition, donc les éléments doivent être distincts.
Merci quand même. :lol3:

Bonjour,

boucle for
rand(6)rand(6)

[Dlzlogic]

Bonjour.
Je ne pense pas que cette méthode marche dans mon cas car ce sont des arrangements sans répétition, donc les éléments doivent être distincts.
Merci quand même. :lol3:

Bonjour,
Si j'étais vous, je ferais l'algorithme et la fonction que vous chercher à avoir, sans chercher à savoir si ça existe dans Maple.

[fatal_error]

c'est un algo qui merite plus qu'un conditionnel!

[Dlzlogic]

c'est un algo qui merite plus qu'un conditionnel!

Oh, mais moi, je veux bien le faire cet algorithme, je cherchais juste à donner une piste à ca34.
Il est vrai que l'utilisation de Maple est citée dans le titre, donc j'aurais dû m'abstenir.

[ca34]

Il y a bien cet algorithme:

Code: Tout sélectionner

restart;
randarr2:=proc(n,k)
local L,A,i,j:
L:=[seq(i,i=1..n)]:
A:=[]:
for i from 1 to k do
j:=rand(1..n+1-i)():
A:=[op(A),L[j]]:
L := subsop(j=NULL,L):
end do:

Mais sur une boucle de quelques millions, c'est moins performant que:

Code: Tout sélectionner

randperm(n)[1 .. k]

qui n'est pas performant puisque c'est pas la peine de chercher une permutation complète pour avoir un arrangement. :hum:
Mais ça va sufir pour ce que je fais. :lol3:

[fatal_error]

peux-tu décrire ce que fait ton algorithme?

[ca34]

Ma foi, je veux bien:
Le but est de choisir aléatoirement k entiers distincts parmi les entiers de 1 à n en tenant compte de l'ordre.
Initialement, il remplit la liste L avec les entiers de 1 à n:

Code: Tout sélectionner

L:=[seq(i,i=1..n)]:

Par la suite, dans la boucle, la liste L contiendra les entiers parmi lesquels on peut encore choisir (il faudra donc éliminer ceux qui ont déjà été choisis).
On initialise la liste A à rien:

Code: Tout sélectionner

A:=[]:

Par la suite, la liste A contiendra les entiers qui ont été choisis.
On fait une boucle de 1 à k pour choisir les k entiers:

Code: Tout sélectionner

for i from 1 to k do

On veut choisir au hasard un entier dans la liste L, dont la longueur est n+1-i. Pour cela, il suffit de choisir un indice j entre 1 et n+1-i:

Code: Tout sélectionner

j:=rand(1..n+1-i)():

On ajoute l'élément L[j] à la fin de la liste A:

Code: Tout sélectionner

A:=[op(A),L[j]]:

On supprime ensuite l'élément L[j] de la liste L (qui contient les éléments qu'il reste à choisir) pour éviter les répétitions:

Code: Tout sélectionner

L := subsop(j=NULL,L):

A la fin de la boucle, A contient un arrangement de k éléments parmi les entiers de 1 à n. :id:
Je crois avoir lu quelque part, que plutôt que de faire un algorithme déterministe comme celui-ci, on peut aussi choisir aléatoirement chaque élément en vérifiant qu'il n'a pas été déjà choisi, et que cette méthode est meilleure. :id2:

[fatal_error]

alors en fait comme maple cest une usine a gaz, chui pret a parier quil sait pas gerer la memoire intelligemment.
donc au lieu de supprimer un elem dans L, tu devrais plutot faire un truc genre
k=rand(n-i) //lindice pioche
A.push(L[k])
if k!= L.length
L[k] = L[L.length]//dernier elem de L remplace celui pioche
fi
Une copie de valeur devrait etre plus rapide que la modif de structure de L.

Ensuite si tu fais des millions de tirages, tas ptet interet a eviter de generer a chaque fois la liste L.

Donc tu crees une variable globale L que tu initialises a seq(1.n)
et une fois que tu as fini de piocher A, tu remets les valeur piochees a la fin de L pour le prochain tirage!

Encore une optim, tu fais k appels a rand (une fois pour i=1, i=2,...i=k) et ce des millions de fois.
il vaut ptet mieux faire un rand(k,500) par exemple qui te genere 500 valeurs entre 1 et k
idem pour rand(k-1,500) etc
et piocher dans le tableau genere a lavance
plutot que faire appel a rand a chaque tirage.


je connais pas la syntaxe mais jpense que tu saisis lidee

[ca34]

OK. Il paraît que la gestion des listes par Maple est très mauvaise.
Je vais tester tes optimisations dès que j'ai le temps (peut-être quelques jours)... :lol3:

[ca34]

Alors j'ai fait une petite modification:

Code: Tout sélectionner

restart;
randarr2 := proc (n, k)
local A, i, j, tampon;
global L;
A := [];
for i from 1 to k do
j := (rand(1 .. n+1-i))();
A := [op(A), L[j]];
if j  n+1-i then
tampon := L[j];
L[j] := L[n+1-i];
L[n+1-i] := tampon
end if
end do;
A end proc;

Et pour l'exécution:

Code: Tout sélectionner

temps := time();
L := [seq(i, i = 1 .. 10)];
for k from 1 to 1000000 do
A := randarr2(10, 5)
end do;
time()-temps

Ceci évite la modificatiuon de structure de L, de plus, avec cette méthode, L contient en permanence les entiers de 1 à n et n'a pas à être réinitialisée à chaque boucle.
Résultat: aucun gain significatif de temps sur 1000000 de boucles.
J'ai aussi essayé de remplacer la liste A par une pile (stack dans Maple): résultat: le temps est allongé.
Quant à générer des tableaux de taille peu élevée qui contiennent des entiers aléatoires, entre 1 et n+1-i pour i=1 à k, je me demande si ça simule bien l'équiprobabilité sur une boucle de 1000000?
Je vais donc m'en tenir à

Code: Tout sélectionner

randperm(10)[1..5]

qui met 3 fois moins de temps.

[fatal_error]

J'ai aussi essayé de remplacer la liste A par une pile (stack dans Maple): résultat: le temps est allongé.
Quant à générer des tableaux de taille peu élevée qui contiennent des entiers aléatoires, entre 1 et n+1-i pour i=1 à k, je me demande si ça simule bien l'équiprobabilité sur une boucle de 1000000?

pourquoi tout comme L, ne pas faire une variable globale A, ce qui evite d'alloc de la mémoire à chaque itération.
de plus il ny a pas besoin de variable tampon.

A[i] := L[j];
L[j] := L[n+1-i];
L[n+1-i] := A[i]

quand à l'équiproba tu peux au pire diviser ta boucle par pas de 500 iterations.

Cela dit, vu qu'on connait pas l'internal de maple ni qu'on sait pas comment il compile les procédures, ca se fait nos optim sont d'un degré négligeable par rapport à sa façon de gérer le script

[ca34]

OK pour A et L.
Comme tu le dis, je crois qu'il ne faut pas considérer Maple comme un langage classique (C, C++, Java...) pour ce genre d'optimisation: on ne sait pas trop comment c'est géré. :mur:
Ce qui m'étonne le plus, c'est que Maple ne prévoie pas ce qu'il faut pour générer des arrangements aléatoires, alors que ça existe pour les combinaisons et les permutations, et que c'est plutôt efficace.

[Dlzlogic]

OK pour A et L.
Comme tu le dis, je crois qu'il ne faut pas considérer Maple comme un langage classique (C, C++, Java...) pour ce genre d'optimisation: on ne sait pas trop comment c'est géré. :mur:
Ce qui m'étonne le plus, c'est que Maple ne prévoie pas ce qu'il faut pour générer des arrangements aléatoires, alors que ça existe pour les combinaisons et les permutations, et que c'est plutôt efficace.

Je suppose que c'est parce que un arrangement est le produit d'une combinaison et d'une permutation.

[ca34]

Oui j'ai aussi testé cette possibilité:

Code: Tout sélectionner

randperm(randcomb(10, 5)

qui est nettement moins efficace que:

Code: Tout sélectionner

randperm(10)[1..5]

Pour une boucle de 1000000 d'arrangements aléatoires, j'obtiens sur ma configuration environ 104s pour la deuxième méthode contre 157s pour la première.
De toute façon, générer une combinaison puis lui appliquer une permutation est beaucoup moins efficace que de générer un arrangement directement: c'est une fonction qui semble manquer chez Maple.

[Dlzlogic]

Oui j'ai aussi testé cette possibilité:

Code: Tout sélectionner

randperm(randcomb(10, 5)

qui est nettement moins efficace que:

Code: Tout sélectionner

randperm(10)[1..5]

Pour une boucle de 1000000 d'arrangements aléatoires, j'obtiens sur ma configuration environ 104s pour la deuxième méthode contre 157s pour la première.
De toute façon, générer une combinaison puis lui appliquer une permutation est beaucoup moins efficace que de générer un arrangement directement: c'est une fonction qui semble manquer chez Maple.

Ce que je voulais dire:
soit 2 nombres m et n
La permutation P = randperm(n)
La combinaison C = randcomb(n,m)
Alors, l'arrangement A = P * C . Il s'agit de la multiplication arithmétique de 2 nombres.

A vérifier l'ordre de m et n.
Sauf, naturellement si je me suis trompé sur le retour de ces fonctions.
Possible que j'ai rien compris depuis le début.

[ca34]

En fait, je me demande si tu ne confonds pas arrangements et nombre d'arrangements?
On a bien le nombre d'arrangements de m éléments parmi n qui est égal au produit .
Mais écrire randperm(m) randcomb(n,m) n'a aucun sens car randperm(m) est une permutation de m éléments, donc ici c'est une liste. Même remarque pour randcomb(n,m) qui est un ensemble. :lol3:

[Dlzlogic]

En fait, je me demande si tu ne confonds pas arrangements et nombre d'arrangements?
On a bien le nombre d'arrangements de m éléments parmi n qui est égal au produit .
Mais écrire randperm(m) randcomb(n,m) n'a aucun sens car randperm(m) est une permutation de m éléments, donc ici c'est une liste. Même remarque pour randcomb(n,m) qui est un ensemble. :lol3:

Oui, effectivement, j'ai fait un contre-sens. Je m'en suis rendu compte après.