CODEWITHSUNDEEP
pythonrandomprobability
Sumit
Sumit

Reputation: 2264

Finding k non contiguous random numbers with uniform probability in the range 1..n

I am trying to find k random numbers in the range 1..n such that none of the k numbers are contiguous. The code I came up with is

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

Update: I know this function won't return the samples with uniform probability. Based on my limited testing, Amber's solution below satisfies both the condition (a) individual elements of the sample are non-contiguous, and (b) all possible k samples (from 1...n) are generated with uniform probability.

Upvotes: 3

Views: 316

Answers (2)

Amber
Amber

Reputation: 526583

The code is simpler if you use a 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

However, as Michael Anderson points out in the comments, this algorithm can fail sometimes in cases where n < 3*k.

A better algorithm that can't fail (and is also faster!) might look like this:

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

The math-fu at the end there is this:

  • 1, the minimum value we can pick
  • plus 1 per number we've picked (index), to account for that picked number
  • plus our position within the skips (which will always increase by at least one)

Thus the result will always increase by at least 2 for each iteration through the loop.

Upvotes: 6

Michael Anderson
Michael Anderson

Reputation: 73480

Here's an unbiased version that won't fail. (But is slower than Ambers solution). If you give it a case with no solution it will loop forever (but thats fixable).

#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

Upvotes: 0

Related Questions