0

長さ N の python のリストがあり、そこから K 個の要素のペアを選択したいのですが、ペア内の要素の繰り返しは許可されておらず、(x,y) == (y,x)(順序は区別されません)。可能な N の選択 2 ペアがあり、K は常に N よりもかなり小さいです。リストから最も「多様な」代表的なペアのセットを選択するための適切な決定論的 (サンプリングなし) の方法は何ですか? (1) のセットリストからのアイテムの最大数が表されているペア (および特定の要素に偏りがない)、(2) ペアのリストがリストの最初または最後に偏っていない場所?

例：

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

5 選択 2 = 10 通りの組み合わせが可能です。2 つのペア (K = 2) を求める場合、ほぼすべての要素がリストに表示され、要素の繰り返しがないため、適切なペアのセットになります。K = 2 のペア[(1,2),(3,4)]の悪い[(1,2),(1,3)]セットは次のようになります: 1 要素を再利用しており、明らかにリストの先頭に偏っているためです。この場合、K が > 2 の場合、要素を繰り返す必要がありますが、これは避けられませんが、代表的/多様な wrt リストでこれを行う方法を見つけたいと考えています。

私は効率的でシンプルなヒューリスティックを探しているだけで、完璧である必要はありません。何か案は？

これには numpy/scipy を使用できます。

4

2 に答える 2

1

少なくともある種の疑似ランダム サンプリングが必要です。そうしないと、ペア サンプリング コードを再実行するときに、最初か最後か、またはどこか別の場所で、常に何らかの「バイアス」が発生します。K が N/2 よりも小さく、N が大きすぎない (1 億以下など) 場合は、次の python コードを使用できます。重複

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 が奇数の場合、これは頭痛の種になりますが、非常に近い単純な近似戦略は、floor(N/2) ペアを繰り返し生成し (重複を回避)、毎回 1 つの数値を使用しないままにすることです。コードは次のとおりです。

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]
于 2013-07-14T00:40:52.417 に答える