Python получить случайные уникальные N пар - PullRequest
Новая
       41

Python получить случайные уникальные N пар

2 голосов
/ 19 марта 2019

Скажите, у меня есть range(1, n + 1).Я хочу получить m уникальных пар.

Я обнаружил, что если количество пар близко к n(n-1)/2 (максимальное количество пар), нельзя просто генерировать случайные пары каждый раз, потому что ониначнется переопределение друг друга.Я ищу несколько ленивое решение, которое будет очень эффективным (в мире Python).

Моя попытка на данный момент: 

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 ]

3 голосов
/ 19 марта 2019

Вы можете использовать combinations для генерации всех пар и sample для случайного выбора.По общему признанию, только ленивый в смысле «не так много, чтобы напечатать», а не в использовании генератора, а не в виде списка: -) 

from itertools import combinations
from random import sample

n = 100
sample(list(combinations(range(1,n),2)),5)

Если вы хотите улучшить производительность, вы можете сделать это ленивым, изучив это Случайная выборка Python с генератором / итерируемым / итератором

генератор, из которого вы хотите сэмплировать, это: combinations(range(1,n)

2 голосов
/ 19 марта 2019

Вот подход, который работает, беря число в диапазоне 0 to n*(n-1)/2 - 1 и декодируя его в уникальную пару элементов в диапазоне 0 to n-1.Для удобства я использовал математику, основанную на 0, но вы, конечно, можете добавить 1 ко всем возвращенным парам, если хотите: 

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)]

Например: 

>>> >>> rand_pairs(5,8)
[(2, 1), (3, 1), (4, 2), (2, 0), (3, 2), (4, 1), (1, 0), (4, 0)]

МатематикаТрудно объяснить, но k в определении decode получается путем решения квадратного уравнения, которое дает число треугольных чисел , которые равны <= i, и где i попадает впоследовательность треугольных чисел говорит вам, как декодировать уникальную пару из нее.Что интересно в этом декодере, так это то, что он вообще не использует n, а реализует взаимно-однозначное соответствие от набора натуральных чисел (начиная с 0) до набора всех пар натуральных чисел.

1 голос
/ 19 марта 2019

Я не думаю, что что-то в твоей линии может улучшиться.В конце концов, когда ваш m все ближе и ближе к пределу n(n-1)/2, у вас будет все меньше шансов найти невидимую пару.

Я бы предложил разделить на два случая: если mмал, используйте ваш случайный подход.Но если m достаточно велико, попробуйте 

 pairs = list(itertools.combination(buffet,2))
 ponits = random.sample(pairs, m)

Теперь вам нужно определить порог m, который определяет путь кода, по которому он должен идти.Тебе нужна математика, чтобы найти правильный компромисс.

...