在R语言中按最小间距随机选取数组元素的最优方法

Hey there! That iterative "reject and retry" approach can definitely get sluggish when you need larger samples—great call looking for a better way. Let’s break down a much more efficient method that directly constructs valid samples without all the trial and error.

First, Verify Feasibility #

Before diving into code, let’s confirm your problem is solvable: to pick 20 elements with at least 15 between each, the minimum required length of your array is 1 + (20-1)*15 = 286. Since your array goes up to 1000, we’ve got plenty of room to work with.

The "Gap Allocation" Method (No Trial-and-Error!) #

This approach works by first creating a base sequence of elements spaced exactly the minimum gap apart, then randomly distributing the extra space in your array across the gaps (including before the first element and after the last). Here’s how to implement it in R:

# Set parameters
set.seed(123)  # Optional: for reproducible results
num_samples <- 20
min_spacing <- 15
max_value <- 1000

# Step 1: Create a base sequence with exactly min_spacing between elements
base_sequence <- seq(from = 1, by = min_spacing, length.out = num_samples)

# Step 2: Calculate how much extra space we have to distribute
extra_space <- max_value - base_sequence[num_samples]

# Step 3: Generate random gaps to fill the extra space
# We need n+1 gaps (before first element, between each pair, after last)
random_gaps <- diff(c(0, sort(runif(num_samples)), 1)) * extra_space

# Step 4: Add the random gaps to the base sequence to get final positions
selected_elements <- base_sequence + cumsum(random_gaps[-length(random_gaps)])

# Optional: Convert to integers if you need whole numbers
selected_elements <- round(selected_elements)

How This Works #

• The base_sequence gives us a starting point where every element is exactly 15 apart (e.g., 1, 16, 31, ...).
• random_gaps splits the extra 714 units (1000 - 286) into 21 random, non-negative chunks (one for each gap in/around the base sequence).
• Adding these gaps to the base sequence shifts elements randomly while preserving the minimum 15-unit spacing.

Verify the Results #

Quick checks to make sure everything works as expected:

# All elements are spaced at least 15 apart
all(diff(selected_elements) >= min_spacing)

# We have exactly 20 elements
length(selected_elements) == num_samples

# No elements exceed 1000
max(selected_elements) <= max_value

Why This Beats Iterative Sampling #

Instead of wasting time generating invalid samples and rejecting them, this method constructs valid samples in linear time (O(n)). Even for much larger sample sizes (like 1000 elements from a 100,000-length array), it’ll run instantly.

内容的提问来源于stack exchange，提问作者Garini