3

どの数字も連続しないようなk範囲で乱数を見つけようとしています。私が思いついたコードは1..nk

def noncontiguoussample(n,k):
    import random
    numbers = range(n)
    samples = []
    for _ in range(k):
        v = random.choice(numbers)
        samples.append(v)
        for v in range(v-1, v+2):
            try:
                numbers.remove(v)
            except ValueError:
                pass

    return samples

更新: この関数は一様な確率でサンプルを返さないことを知っています。私の限られたテストに基づいて、以下のアンバーのソリューションは、(a) サンプルの個々の要素が連続していないこと、および (b) すべての可能な k 個のサンプル (1...n から) が均一な確率で生成されるという条件の両方を満たします。

4

2 に答える 2

6

を使用すると、コードはより簡単になりますset。

import random

def noncontiguoussample(n,k):
    numbers = set(range(1,n+1))
    samples = []
    for _ in range(k):
        v = random.choice(list(numbers))
        samples.append(v)
        numbers -= set([v-1, v, v+1])
    return samples

ただし、Michael Anderson がコメントで指摘しているように、このアルゴリズムは、n < 3*k.

失敗することのない (そしてより高速な) より優れたアルゴリズムは、次のようになります。

import random

def noncontiguoussample(n,k):
    # How many numbers we're not picking
    total_skips = n - k

    # Distribute the additional skips across the range
    skip_cutoffs = random.sample(range(total_skips+1), k)
    skip_cutoffs.sort()

    # Construct the final set of numbers based on our skip distribution
    samples = []
    for index, skip_spot in enumerate(skip_cutoffs):
        # This is just some math-fu that translates indices within the
        # skips to values in the overall result.
        samples.append(1 + index + skip_spot)

    return samples

最後の数学フーはこれです：

  • 1、選択できる最小値
  • index選択した番号 ( )ごとに 1 を加えて、その選択した番号を説明します。
  • 加えて、スキップ内での位置 (常に少なくとも 1 つ増加します)

したがって、結果は常に、ループの反復ごとに少なくとも 2 ずつ増加します。

于 2012-09-27T07:07:14.890 に答える
0

これは、失敗しない公平なバージョンです。(ただし、Ambers ソリューションよりも遅い)。解決策のないケースを指定すると、永久にループします (ただし、修正可能です)。

#A function to check if the given set is OK
def is_valid_choice( s ):
  for x in s:
    if x-1 in s or x+1 in s:
      return False
  return True

#The real function
def noncontiguoussample(n,k):
  while True:
    s = random.sample(xrange(1,n+1),k)
    if is_valid_choice(s):
      return s
于 2012-09-27T09:00:12.500 に答える