Disons que j'ai une plage de (1, n + 1) . Je veux obtenir m paires uniques.
Ce que j'ai trouvé, c'est que si le nombre de paires est proche de n (n-1) / 2 (nombre maximum de paires), on ne peut pas simplement générer des paires aléatoires à chaque fois car elles commenceront à se remplacer. Je recherche une solution un peu paresseuse, qui sera très efficace (dans le monde de Python).
Ma tentative jusqu'à présent:
def get_input(n, m):
res = str(n) + "\n" + str(m) + "\n"
buffet = range(1, n + 1)
points = set()
while len(points) < m:
x, y = random.sample(buffet, 2)
points.add((x, y)) if x > y else points.add((y, x)) # meeh
for (x, y) in points:
res += "%d %d\n" % (x, y);
return res
3 Réponses :
Vous pouvez utiliser des combinaisons pour générer toutes les paires et utiliser sample pour choisir au hasard. Certes, seulement paresseux dans le sens "pas grand chose à taper", et pas dans l'utilisation d'un générateur pas dans le sens d'une liste :-)
from itertools import combinations from random import sample n = 100 sample(list(combinations(range(1,n),2)),5)
Si vous voulez améliorer les performances, vous pouvez le rendre paresseux en étudier cela Échantillon aléatoire Python avec un générateur / iterable / itérateur p>
le générateur à partir duquel vous voulez échantillonner est le suivant: combinations(range(1,n)
Je ne pense pas que quelque chose sur votre ligne puisse s'améliorer. Après tout, à mesure que votre m se rapproche de plus en plus de la limite n (n-1) / 2 , vous avez de plus en plus de chances de trouver la paire invisible.
Je suggérerais de diviser en deux cas: si m est petit, utilisez votre approche aléatoire. Mais si m est assez grand, essayez
pairs = list(itertools.combination(buffet,2)) ponits = random.sample(pairs, m)
Vous devez maintenant déterminer le seuil de m qui détermine quel code chemin à suivre. Vous avez besoin de quelques calculs ici pour trouver le bon compromis.
Voici une approche qui fonctionne en prenant un nombre dans la plage 0 à n * (n-1) / 2 - 1 et le décode en une paire unique d'éléments dans la plage 0 à n-1 . J'ai utilisé des mathématiques basées sur 0 pour plus de commodité, mais vous pouvez bien sûr ajouter 1 à toutes les paires renvoyées si vous le souhaitez:
>>> >>> rand_pairs(5,8) [(2, 1), (3, 1), (4, 2), (2, 0), (3, 2), (4, 1), (1, 0), (4, 0)]
Par exemple:
import math
import random
def decode(i):
k = math.floor((1+math.sqrt(1+8*i))/2)
return k,i-k*(k-1)//2
def rand_pair(n):
return decode(random.randrange(n*(n-1)//2))
def rand_pairs(n,m):
return [decode(i) for i in random.sample(range(n*(n-1)//2),m)]
Y a-t-il un lien vers une explication plus complète? Merci.
C'est parfait au fait.
@AfonsoMatos Je ne connais pas de lien. J'ai commencé par l'énumération (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3) (qui est le genre d'énumération dont vous avez besoin si cela ne dépend pas de n ) a remarqué que là était 1 qui commençait par 1, 2 qui commençait par 2, etc. Pour obtenir la paire de i , j'avais besoin de savoir dans quel "bloc" i se trouve. i = 7 , par exemple est dans le bloc 4 car 1 + 2 + 3 <= 7 <1 + 2 + 3 + 4 qui traduit à 3 (3-1) / 2 <= 7 <4 (4-1) / 2 Si vous résolvez 7 = k (k-1) / 2 et tournez à un entier, vous obtenez le k . Un peu plus d'algèbre vous permet d'obtenir l'autre index.