Получение самого «разнообразного» набора пар из списка в Python?

Question

У меня есть список в python длины N, и я хочу выбрать из него пары пар элементов, где повторение элементов внутри пары недопустимо и где (x,y) == (y,x) (без учета порядка). Есть N выбрать 2 пары, и K всегда значительно меньше N. Что такое хороший детерминированный способ (без выборки), чтобы выбрать самый «разнообразный» и представительный набор пар из списка, что означает: (1) набор пар, где представлено наибольшее количество элементов из списка (и нет какого-либо смещения для какого-либо конкретного элемента), (2) и где список пар не смещен в сторону начала или конца списка?

пример:

l = [1,2,3,4,5] 

есть 5 выбрать 2 = 10 возможных комбинаций. Если мы попросим 2 пары (K = 2), набор хороших пар будет [(1,2),(3,4)], потому что почти каждый элемент появляется в списке и у нас нет повторений любого элемента. A Плохой набор пар для K = 2 будет: [(1,2),(1,3)], поскольку он повторно использует 1 элемент и явно предвзято относится к началу списка. Если бы K было> 2, в этом случае нам нужно было бы повторять элементы, это неизбежно, но я хочу найти способ сделать это, что является репрезентативным/разнообразным списком wrt.

Я просто ищу эффективную и простую эвристику, не обязательно должен быть совершенным. есть идеи?

счастлив использовать numpy/scipy для этого.

Answer 1

Вам потребуется, по крайней мере, псевдослучайная выборка, или всегда будет какая-то «предвзятость» при повторном запуске кода выборки пары, будь то начало или конец или где-то еще. Если K меньше, чем N/2, и если N не слишком велико (скажем, 100 миллионов или меньше), вы можете использовать следующий код python, который избегает повторных вызовов выборки, потому что он генерирует K псевей-случайные пары одновременно, избегая дублирует

import random 

X = range(N) 

random.seed() # uses system time to initialize random number generator, or you can pass in a deterministic seed as an argument if you want 

# code to use to generate K pairs 
A = random.sample(X,2*K) # now you have a list of 2*K unique elements from 0 to N-1 
pairs = zip(A[0:K],A[K:(2*K)]) # now you have your pairs 

Теперь, если K больше, чем N/2, то вы будете иметь дубликаты, но вы можете свести к минимуму подобные дубликаты выше, просто перезапустив код, аналогичный 2 строки выше в цикле. Если N является нечетным, это создает головные боли, но простая очень близкая приблизительная стратегия состоит в том, чтобы многократно генерировать пары (N/2) (избегая дубликатов) и просто оставлять одно число неиспользованным каждый раз. Код следует:

pairs = [] 
M = N 
if M % 2 == 1: 
    M -= 1 
while len(pairs) < K: 
    B = random.sample(X,M) 
    A = zip(B[0:(M/2)],B[(M/2):M]) 
    pairs.extend(A) 
pairs = pairs[0:K] 

Answer 2

Возьмите первые матчи K от round-robin tournament? Перечислите список псевдослучайным перемещением Фишера-Йейта с детерминированным семенем, чтобы избежать смещения к концам.