Algorithme pour la génération aléatoire de paires de nombres

Bonjour

J’essaie de trouver un algorithme qui me permettrait efficacement de générer des paires de nombres de façon aléatoire depuis une liste de nombres définit.

Je m’explique:

J’ai une liste de nombres discontinues nommée N (ex: { 1, 2, 3, 6, 8, 10}), et j’ai besoin de former des paires de nombres aléatoirement pour les ajouter dans une liste. (une paire ne peux se trouver qu’une seule fois dans la liste)

Par exemple, avec une liste N de 3 nombres différent, il y a 6 paires possible (on ne prend pas en compte les paires qui contiennent 2 fois le même nombre):

Exemple pour une liste N = { 4, 8, 9 }, les paires possibles sont:

(4,8) (4,9) (8,4) (8,9) (9,4) (9,8)

Quand on arrive a une liste N avec 30 nombres à l’intérieur, on obtient 870 paires possibles et ma méthode actuelle devient de moins en moins performante plus j’ajoute de nombres à N.

Pour l’instant ma stratégie c’est ça:

// taille de N est 30 pour cet exemple, donc 870 paires possibles
N = { 3, 8, 10, 15, 16, ... }

// disons que j'ai déjà 200 paires dans ma list
my_pairs = { (8,16), (23, 32), (16,10), ... }

// on sélectionne 2 nombres de N aléatoirement
rn1 = random(N)
rn2 = random(N)

On parcours my_pairs pour checked si il y a déjà une paire (rn1,rn2)
    
Si la paire existe déjà, on choisit 2 nouveau nombres pour rn1 et rn2 et on recommence le check de la liste

Si la paire n'existe pas, on l'ajoute à la liste my_pairs

Le problème est que plus il y a de paires dans 'my_pairs’, plus je vais aléatoirement générer de paires qui existent déjà et donc a chaque fois je dois parcourir la liste pour check l’existence de la paire dans my_list.

Je pourrais essayer de générer toutes les paires possibles depuis N dans une liste, mélanger aléatoirement la liste et récupérer 1 élément de la liste à chaque fois mais ça prendrais pas mal de mémoire de stocker l’entièreté des paires possibles (9900 paires possibles pour une liste N de 100 nombres) 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.

Est ce qu’il y a un algorithme qui me permettrait générer des paires uniques aléatoirement et différentes à chaque fois ?

Je pensais peut être qu’utiliser des matrices pourrait être utile, ou classer les paires dans une structure ordonnée à chaque fois que je les ajoutes à ma liste.

C’est en quel langage de programmation ? Parce que déjà, si c’est en Python, tu peux utiliser un set pour stocker tes pairs, ce sera un peu plus rapide à parcourir.

Est-ce que tes pairs sont stockées quelque part ou est-ce que tu regénères ta liste à chaque exécution du code ?

Dans le premier cas, tu peux éventuellement choisir de séparer nouveaux nombres et anciens nombres, comme ça tu génères des paires avec obligatoirement un nouveau nombre. Tu peux donc créer une liste spécifique pour les nouvelles paires, que tu ajoutes à l’autre à la fin.

Également, avec un set, tu peux te passer de vérifier sa présence dans la liste. Les sets ne prennent pas les doublons. Il te suffit de boucler le nombre de ofis que tu veux, ou jusqu’à ce que ton set ait la taille souhaitée, par exemple.

Est-ce que $N$ deviendra trop grand pour tous les stocker en mémoire ?

Car sinon, tu peux juste tous les générer et ensuite tu les mélanges.

Tu as différents scénarios possibles, plus ou moins efficaces selon les proportions.

• Scénario 1- la proposition de Ache.

• Scénario 2- Tu as besoin de générer N paires. Tu en génères N(voire un peu plus) aléatoirement, sans tester si il y a des doublons. Puis tu executes un processus pour supprimer les doublons. Et tu boucles si il en manque. Si tu dois générer N paires, sur P paires possibles, et si N/P est relativement petit, ça sera efficace. Mais très mauvais si N est proche de P.

Si N est proche de P, il faudrait en fait tirer aléatoirement les paires qui ne seront pas dans la sélection finale. Peu de paires à sélectionner, facile…

• Scénario 3 - basé sur la proposition de Ache, mais adapté pour les cas où le tableau est trop grand pour tenir en mémoire. Pour chaque élément A, tu sélectionnes aléatoirement x éléments B ( tous différents 2 à 2, et tous différents de A). Tu crées donc un extrait de la liste de toutes les paires possibles. Tu choisis le nombre x suffisamment petit pour que le tableau obtenu tienne en mémoire, mais le plus grand possible quand même, pour que le résultat obtenu ne soit pas biaisé par la méthode.

Et ensuite, tu sélectionnes aléatoirement N paires distinctes parmi ce tableau déjà aléatoire.

Par rapport au scénario 3, tu peux du coup prendre B > A, si ta liste ste ordonnée, ou indice B > indice A sinon.

Je le fait en C mais ça reviens au même que pour d’autre languages de prog.

Mes paires sont stockées dans une liste qui reste en mémoire et je viens ajouter de nouvelles paires aléatoire dans cette meme liste.

Le soucis je pense c’est que un nombre contenu dans N peux avoir plusieurs paires ex: (5,8), (5,10), (5,13). Donc je peux pas le mettre de coté après l’avoir généré 1 fois. (Si j’ai bien compris ta méthode)

Meme en python, à mon avis le set en interne check avec tout les autres membres du set du coup ça devrais être l’équivalent de la méthode que j’ai actuellement.

Oui, comme je l’ai dit plus haut, le nombres de paires possible devient trop grand, avec la liste N de taille 100, il y a 9900 paires possibles. Pour taille N = 500 y’a ~250 000 paires possibles (le nombre de paires possible est égale à (taille N) * (taille N - 1) ).

Meme en python, à mon avis le set en interne check avec tout les autres membres du set du coup ça devrais être l’équivalent de la méthode que j’ai actuellement.

Ben justement non, les sets en Python utilisent une table de hashage pour obtenir un coût amorti du look-up en $O(1)$. Tu pourrais utiliser une implémentation existante d’un hash set en C, ça doit se trouver quelque part.

Oui c’est quelque chose comme ça que je cherchais, une façon de représenter le tableau de façon linéaire sans avoir a générer toutes les paires. Le seul soucis c’est qu’il va juste manquer les paires inverses avec cette méthode ( (3,5) -> (5,3) ) mais j’imagine que je peux contourner ça en représentant une paire d’indice négatif (-x) comme l’inverse de la paire x.

edit: Le seul problème c’est que je peux pas avoir l’inverse de la paire d’indice 0.

Pour 5 éléments il devrais y avoir 20 paires. Pour cet exemple il manquerait les paires:

• 2, 1
• 3, 2
• 4, 3
• 5, 4
• 3, 1
• 4, 2
• 5, 3
• 4, 1
• 5, 2
• 5, 1

(qui sont basiquement les inverses respectifs des paires générer.)

Dis, c’est pour quoi faire, tout ça ?

Ah, je n’ai pas pris en compte que tu voulais aussi les inverses. Je partais du principe que {1, 2} et {2, 1} étaient égaux.

Dans ce cas ce n’est pas compliqué, si x > n*(n -1)/2, alors tu swap, et le tour est joué.

Bon je pense avoir en partie trouver une solution à mon problème. J’ai encore des tests à faire dessus et il faut aussi vérifier que ce soit assez performant.

En partant de l’idée de @QuentinC de pouvoir générer une paire depuis un nombre x, j’ai créé la fonction suivante: (le code est en python)

from math import ceil

def get_pair(x):
    n = 0.5+sqrt(0.25+2*x)
    nb = ceil(n) - 1    
    return (ceil(n), round(nb * (n -nb)))

ça me permet de générer des paires à l’infini de façon ordonnées tel que:

id x:  1  2  3  4  5  6  7  8  ...
       |  |  |  |  |  |  |  |  
paire: 2  3  3  4  4  4  5  5  ...
       1  1  2  1  2  3  1  2  ...

Et j’utilise les nombres contenu dans les paires comme positon du nombre à récupérer dans ma liste de nombres N.

Maintenant que je peux récupérer une paire à partir d’un nombre, j’ai juste qu’à choisir un nombre random entre 1 et le nombre max de paires possibles.

Pour ne pas avoir à choisir une paire random puis check si elle est déjà dans ma liste de paires puis rechoisir une paire random, j’attribue un id à chaque paires que je génère puis le prochain nombre random pour récupérer une paire sera choisis entre [nombre de paires que j’ai déjà , nombre de paires possible].

Cet id ainsi que la position de la paire dans ma liste de paires sera ensuite utilisé pour générer les paires suivantes et éviter les paires dupliquées.

Voici le code complet, avec une liste de nombres N où on génère progressivement, de façon aléatoire, toutes les paires possibles de N:

from math import sqrt, ceil
from random import randint

# renvoie une paire à partir d'un nombre entier
def get_pair(x):
    n = 0.5+sqrt(0.25+2*x)
    nb = ceil(n) - 1    
    return (ceil(n), round(nb * (n -nb)))

# fonction récursive qui retourne l'index à associé a la paire que l'on souhaite ajouter
# en regardant si l'index n'est pas déjà présent dans P_index
def check_pair(I, x):
    new_index = 0
    for i in range(1, len(I)+1):
        if I[i-1] == x:
            I[i-1] = 0
            new_index = check_pair(I, i)
            if new_index == 0:
               return i
            return new_index
    return new_index

# liste des nombres à mettre en paires
N = [ 2, 3, 4, 5]

# liste de paires
P = []

# index des paires
P_index = []

# on loop 6 fois pour ajouter le maximum de paires à P
for i in range(1, 7):
    # nombre aléatoire entre i et 6 (nombre maximum de paires)
    # donc a chaque fois qu'on récupère une paire, 
    r_pair = randint(i, 6)
    
    index = check_pair(P_index, r_pair)

    # si l'index équivaut à 0 alors la paire n'a pas déjà été ajouté à P
    if index == 0:
        P.append(get_pair(r_pair))
        P_index.append(r_pair)
    else:
        P.append(get_pair(index))
        P_index.append(r_pair)

# affiche les paires dans P
for paire in P:
    print(f'( {N[paire[0]-1]}, {N[paire[1]-1]} )')

ça me parait pas mal pour gérer les cas extrêmes où mon nombre de paires s’approche du nombre de paires maximum et ça a le mérite de générer une paire aléatoire qu’une seule fois.

La seule chose qui reste à ajouter c’est l’inverse des paires ( ex: (4,1) -> (1,4) ) mais en modifiant un peu ce code, ça ne devrait pas être trop compliqué.

Qu’est ce que vous en pensez ?

Dis, c’est pour quoi faire, tout ça ?

@Moté ça fait parti d’un projet d'algorithme génétique que je suis en train de programmer et dont j’ai besoin d’associer des identifiants de "genes" entre eux.

En Python, j’ai une règle : Toutes les boucles peuvent être remplacées par des traitements de listes ou de tableaux, et on gagne énormément en performance.

En gros, une boucle sur 1000 éléments, remplacée par une opération sur un tableau … tu divises le temps de traitement par 100.

Ici, tu as la commande random.sample ( range(n*(n-1)), k ) , qui fait tout le job. Sélection de k éléments, sans doublon, dans le range imposé.

Je propose ça :

import random
import numpy

n = 5
n1= n-1
k=16
ll = random.sample( range(n*(n-1)), k)
ll2 = numpy.array(ll)

ll_x = numpy.trunc(ll2/(n-1))  # pour chaque élémént de ll2, je cherche la valeur de x  
ll_y = ll2 - (n-1)*ll_x        # et par différence, je cherche la valeur de y     A ce niveau,    
ll_w = ll_y>=ll_x              # pour chaque couple x,y , w me dit si y>= x
ll_z = ll_y + ll_w             # Et dans ce cas, j'ajoute 1 à y , pour ne pas avoir de point tel que x=y, et pour avoir des pts tels que y=n-1
print(ll_x)
print(ll_y)
print(ll_w)
print(ll_z)                    # ll_x et ll_z donnent respectivement les x et les y recherchés

On doit pouvoir combiner ces 2 arrays, en un seul array de couples, mais je ne connais pas.

J’aime bien ta méthode @elegance, elle est très … élégante

Mais bien que concise, je ne pense pas qu’elle soit optimale parce qu’avec les opérations effectué sur les tableaux, numpy viens les parcourir à chaque fois pour les modifier (je pense, je ne sais pas exactement comment fonctionne numpy en interne). En tout cas sur ma machine, j’ai fais quelques tests et cette méthode apparait plus lente que celle que j’ai poster précédemment. (ex: pour n=8 et k=21 j’obtiens ~45ms avec ta méthode et ~21ms avec le code que j’ai poster)

De plus, le petit soucis c’est j’ai besoin de d’ajouter des paires une par une et entre chaque création de paire, la valeur de n peux augmenter, ce qui deviens un peu embêtant avec ces opérations de tableaux pour pouvoir générer de nouvelles paires.

J’ai quand même été intrigué par ton code @elegance, du coup je suis aller check le code source de python pour la fonction random.sample() (cette partie là) et j’ai trouvé très intéressante la façon dont ils mélangent aléatoirement une liste d’éléments. Ça reviens à peu près à ma méthode check_pair() mais mieux et la syntaxe est plus belle.

Voila le code après avoir intégré leurs façon de faire:

N = [ 1, 2, 3, 4, 5, 6, 7, 8]
P = []
P_index = []
k = int(len(N)*(len(N)-1)/2) # nb max de paires

for i in range(1, k+1):
    x = randint(1, k)
       
    while x in P_index:
        x = randint(1, k)
    
    P_index.append(x)
    P.append(get_pair(x))

# affiche les paires de P
for paire in P:
    print(f'( {N[paire[0]-1]}, {N[paire[1]-1]} )')

C’est sûr, maintenant c’est beaucoup plus compacte. Après, à voir si ça fait une grosse diff niveau performances.

edit: Je viens juste de me rendre compte que leurs méthode est pas si bien que ça (pour mon cas), enfaite ils génèrent tout un tas de nombres aléatoires et ils check s’ils ont déjà été généré. Ce qui fonctionne bien quand tu n’as pas beaucoup d’élément mais qui peux devenir un cauchemar si t’en as trop (le programme essaierait en continue de générer des nombres aléatoires). Ils expliquent en commentaire que pour un grand nombre d’éléments ils utilisent une méthode (lien du code) presque similaire à celle que j’ai employé dans check_pair().

petit + du coup, sans les loop en python le code de check_pair (qui devrait s’appeler recherche_paire plutôt), ça donne:

def check_pair(I, x):
    if x in I:
        ind = I.index(x)+1
        I[ind-1] = 0
        new_index = check_pair(I, ind)
        if not new_index:
            return ind
        return new_index
    return 0

Il fait exactement la même chose que l’ancien check_pair, mais apparemment avec python ça fait la diff parce qu’apparemment il est 3x plus rapide …

L’avantage de la fonction 'intégrée' random.sample, c’est que, justement, elle est intégrée. Donc elle est compilée. Je ne pratique pas du tout Python, mais j’ai beaucoup entendu que Python n’est efficace sur des gros volumes que si on manipule des tableaux, et pas les éléments 1 par 1 dans des boucles.

Mais j’ai l’impression que ta demande a évolué. Si tu as 8 éléments différents (ton dernier traitement), tu as 8*7=56 paires possibles. Tu divises par 2 … parce que finalement, tu considères que (a,b) et (b,a), c’est la même paire ? Accessoirement, la fonction partie entière est inutile, le produit de 2 entiers consécutifs est forcément pair. Et donc tu calcules la partie entière d’un entier.

Donc tu as 28 (ou 56 ?) paires possibles.

Et tu veux un traitement qui renvoie ces 28 paires, dans un ordre aléatoire.

Ta demande n’est plus une sélection aléatoire, mais un ordre aléatoire.

Et dans la collection des outils tout faits pour ça, ce n’est plus random.sample, mais random.shuffle

Non ma demande est la même depuis le début, dans mon code je génère toutes les paires possibles à titres d’exemple mais comme je l’ai dis avant, je ne vais pas toute les ajouter directement mais progressivement avec un nombre d’élément qui peux varier.

dans l’exemple je n’utilise que 28 paires parce que le code ne prend pas en compte les paires inverses actuellement (comme je l’ai dis avant) mais une fois que le code est valide sans les paires inverse, il y a juste a faire quelques modif pour intégrer les paires inverses. C’est pour ça que je voulais déjà vérifier que le code était bon.

Ok, tu fais une sorte de numéro de série aléatoire et tu veux pas avoir de doublon ?
J’ai juste ?

@ache c’est plutôt que j’ai des éléments et chaque paire représente une connection entre eux. Au début je commence avec peu d’éléments et peu de connections et au fur et à mesure j’ajoute des éléments et des connections entre eux.

@CactusHaven, ça ressemble beaucoup à un graphe orienté ce que tu décris me semble-t-il.

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.