Chaque élément de ta liste représentant un noeud, tu pourrais mémoriser au niveau de chacun d’eux les relations créées aléatoirement avec les autres. De cette manière tu n’as à vérifier l’existence des relations qu’au niveau du noeud source, choisi aléatoirement en premier, au lieu de vérifier l’ensemble des relations déjà créées.
Et à chaque fois que N augmente, tu crées alors autant de noeuds sans relation que nécessaire.
Pour n=8, tu as 8x7=56 éléments 'possibles’. Tu les tries de façon aléatoire (tous, puisqu’à terme à la fin du process, tu les veux tous). Donc méthode SHUFFLE. Et tu parcours le tableau obtenu dans l’ordre.
Si tu crées un tableau, en ajoutant 1 à 1 les éléments, vers la fin, quand tu vas tirer aléatoirement un nombre et tester si ce nombre n’a pas déjà été choisi, ça risque de prendre un temps très long. Imagine ce que donne ta boucle while x in p_index quand tu as un tableau de 1 Million d’éléments, et les seuls éléments pas dans p_index sont au nombre de 1 ou 2 !
@fromvega oui effectivement les données peuvent être représentées sous forme de graphe orienté. Et j’ai pensé à la méthode que tu as décris pour ajouter des relations aléatoirement. Ça fonctionne bien et c’est la seconde technique que j’utilise avec celle présenté dans mon premier post ici.
Le seul soucis avec cette approche est que certaines relation auront plus de chance d’être ajoutées que d’autres.
Par exemple si j’ai 4 nœuds { A, B, C, D } (donc 3 connections possible par nœud) et que on prend le nœud A qui a déjà 1 connection et le noeud B qui n’as pas de connections, on obtient:
P_n = Probabilité de choisir un nœud = 1/4 (1 chance sur 4 de choisir tel nœud)
P_c = Probabilité de choisir une connection d'un nœud
on a:
pour le nœud A: P_c = P_n + 1/2 (il n'y a que 2 connections disponible pour le nœud A)
pour le nœud B: P_c = P_n + 1/3 (il y a 3 connections disponible pour le nœud B)
En gros, plus un nœud a de connections existantes, plus le reste des connections du noeud ont une forte probabilité d’être sélectionnées.
En cas pratique je ne sais pas vraiment si ça fausse la selection aléatoire de nouvelles connections (c’est pour ça que je l’utilise en partie), mais le fait est que les connections n’ont plus exactement les même chances d’être ajoutées.
Imagine ce que donne ta boucle while x in p_index quand tu as un tableau de 1 Million d’éléments, et les seuls éléments pas dans p_index sont au nombre de 1 ou 2 !
@elegance oui je me suis rendu compte de ça, c’est pour ça que j’ai expliqué ensuite que cette méthode ne marche pas du tout et que la précédente restait le meilleur choix.
Pour n=8, tu as 8x7=56 éléments 'possibles’. Tu les tries de façon aléatoire (tous, puisqu’à terme à la fin du process, tu les veux tous). Donc méthode SHUFFLE. Et tu parcours le tableau obtenu dans l’ordre.
Le problème c’est que la valeur de n augmente, donc avec cette méthode je dois regénérer le tableau de toutes les paires possibles à chaque fois que la taille de n augmente, ce qui n’est pas trop une option, surtout qu’ensuite je ne peux pas parcourir ce tableau dans l’ordre.
Ta demande a quand même évolué depuis le début, parce que maintenant tu dis que le nombre d’éléments peut augmenter au fur et à mesure des tirages.
Dans ce cas, ma technique ne fonctionne plus très bien non plus, dans le sens où la paire à l’index x n’est plus la même si n a changé entre temps et tu serais obligé de faire un mapping compliqué si tu veux conserver ce qui a déjà été tiré.
A noter tout de même après quelques petits essais que ma méthode est à priori généralisable pour des triplets, quadruplets, ….. mais à condition que le nombre d’éléments soit constant pendant l’ensemble des tirages.
Un mathématicien spécialiste des énumérations doit pouvoir le démontrer je pense.
Le problème c’est que la valeur de n augmente, donc avec cette méthode je dois regénérer le tableau de toutes les paires possibles à chaque fois que la taille de n augmente, ce qui n’est pas trop une option, surtout qu’ensuite je ne peux pas parcourir ce tableau dans l’ordre.
Pourquoi ce n’est pas une option de regénérer la liste des paires possibles ?
Tu peux te servir de ma méthode pour le faire en O(n^2).
Avec 100 éléments tu es certaintement loin du stade où c’est vraiment prohibitif.
Ensuite pour pouvoir conserver l’ordre de ce qui a déjà été vu, tu as deux solutions. La deuxième est probablement plus simple:
Tu génères uniquement les nouvelles paires qui n’existent pas dans le tableau (c’est là le plus compliqué)
Tu mélanges uniquement la sous-partie du tableau qui n’a pas encore été vue
Ou bien:
Tu génères toutes les paires que tu ranges dans un set
Tu supprimes du set les paires qui ont déjà été vues (je te suggère un set car l’opération se fera en O(n) ou O(n*log(n)) au lieu de O(n^2) pour un tableau)
Tu transvases le set dans ton tableau que tu pourras ensuite mélanger. Si besoin tu le prepend par ce qui a déjà été vu.
Dans tous les cas, évite les algorithmes avec boucle du genre je tire des éléments jusqu’à ce que j’en tire un que je n’ai encore jamais vu.
C’est un anti-pattern classique totalement imprévisible dont la performance empire à chaque tirage, et c’est précisément pour éviter ce genre de chose qu’on recommande la fonction shuffle.
Ta demande a quand même évolué depuis le début, parce que maintenant tu dis que le nombre d’éléments peut augmenter au fur et à mesure des tirages.
Non ça je l’ai dis depuis le début:
… et en plus de ça la taille de N augmente progressivement donc je peux pas trop recalculer la liste des paires possible à chaque fois que j’ajoute un nombre à N.
Dans ce cas, ma technique ne fonctionne plus très bien non plus, dans le sens où la paire à l’index x n’est plus la même si n a changé entre temps et tu serais obligé de faire un mapping compliqué si tu veux conserver ce qui a déjà été tiré.
C’est pour ça que je l’ai modifié en une fonction qui map les paires entre elles indépendamment du nombre de d’éléments dans N. (voir la fonction get_pair() dans ce post)
Ensuite, au risque de me répéter, je ne vais pas générer l’ensemble des paires possible, imaginons que j’ai 500 éléments dans N, ça fait ~250 000 paires possibles ce qui prend beaucoup de mémoire ainsi que de temps à générer et ultimement dans ce cas la je n’utiliserais pas vraiment la totalité des paires possibles. (autant du coup utiliser ma fonction get_pair())
Donc, voilà un exemple de code qui (à mon avis), conviendrait le mieux au problème :
from math import sqrt, ceil
from random import randint
defget_pair(x):
n = 0.5+sqrt(0.25+2*x)
nb = ceil(n) - 1return (ceil(n), round(nb * (n -nb)))
defcheck_pair(I, x):if x in I:
ind = I.index(x)+1
I[ind-1] = 0
new_index = check_pair(I, ind)
ifnot new_index:
return ind
return new_index
return0defadd_random_pair(pair_list, pair_index, nb_item):
k_max = int(nb_item*(nb_item-1)/2) # Nombre de paires possible
r_pair = randint(len(pair_list), k_max)
index = check_pair(pair_index, r_pair)
if index == 0:
pair_list.append(get_pair(r_pair))
else:
pair_list.append(get_pair(index))
pair_index.append(r_pair)
N = [ 2, 5, 7, 8, 10 ] # Notre liste d'éléments
N_size = len(N)
P = [] # On stocke les paires ici
P_index = []
# On ajoute 3 paires
add_random_pair(P, P_index, N_size)
add_random_pair(P, P_index, N_size)
add_random_pair(P, P_index, N_size)
# On peux continuer à ajouter des nombres à N ou des paires avec add_random_pair()
N.append(13)
N_size = len(N)
add_random_pair(P, P_index, N_size)
add_random_pair(P, P_index, N_size)
# ...# Affiche les paires dans Pfor paire in P:
print(f'( {N[paire[0]-1]}, {N[paire[1]-1]} )')
Par contre, ça ne prend pas en compte les paires inverses (a,b) (b,a), mais ça ne devrait pas être trop dur à implémenter en modifiant ce code.
Du coup, pour mon projet, je vais soit utiliser cette méthode qui est très bien pour gérer les cas extrême et fonctionne relativement bien pour le reste, ou sinon rester sur la méthode du premier post mais avec un hashset et la fonction get_pair() pour récupérer des paires; cette méthode fonctionne bien jusqu’à ~80% des paires possibles (et encore je suis large là), donc je l’utiliserais de façon hybride avec la méthode de graphe orienté décrit par @fromvega.
Merci à tous pour votre aide!
Je marque ce sujet résolu mais si quelqu’un à d’autres solutions ou des améliorations à apporter, je suis toujours intéressé.
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
