Как мы можем эффективно генерировать k случайные и не последовательные выборки из [1,...,N]?
Не желаемый пример с (N=10, k=4):
2,3,8,10
Это не является желательным примером, поскольку 2 и 3 являются последовательными.
Желаемый пример с (N=10, k=4):
2,6,8,10
Это хороший пример, поскольку разница между каждой парой образцов больше, чем 1
sort(randperm(N-(k-1),k))+[0:(k-1)]
Для этого решения есть простое оберванство, если вы принимаете какое-либо решение по вашей проблеме и вычитаете [0:(k-1)], вы получаете случайный выбор k чисел из N-(k-1)
Обозначим через S множество всех векторов k -элементов со значениями, взятыми из [1,...,N], которые не имеют никаких последовательных значений. Для случайного выборки с распределением единообразного по S можно использовать метод отклонения:
В Matlab легко генерировать равномерно распределенные векторы k -элементов со значениями, взятыми из [1,...,N] без замены (функция randsample). Таким образом, это используется как пространство выборки T:
k = 4;
N = 10;
result = [1 1]; % // just to get while loop started
while any(diff(result)<=1) % // does not meet condition: try again
result = sort(randsample(N, k).'); %'// random sample without replacement
end
Класс Python, который правильно проверяет каждую пару образцов. Вы несете ответственность за то, что не передали ему набор чисел, что невозможно, хотя (например, N = 10, k = 100).
>>> class NonConsecutiveSampler(object):
def __init__(self,N):
import random
self.num = N
def get_samples(self,k):
possibilities = [i for i in range(1,self.num + 1)]
samples = []
while len(samples) < k:
r = random.sample(possibilities,1)[0]
samples.append(r)
for i in range(r - 1, r + 2):
if i in possibilities:
possibilities.remove(i)
samples.sort()
return samples
>>> n = NonConsecutiveSampler(10)
>>> n.get_samples(4)
[2, 5, 8, 10]
>>> n.get_samples(4)
[1, 5, 7, 10]
>>> n.get_samples(4)
[3, 6, 8, 10]
>>> n.get_samples(4)
[1, 3, 5, 8]
РЕДАКТИРОВАТЬ: он стал намного более эффективным
Вы можете сделать приращение между выборками, равномерно распределенными между 2 и N-1 (чтобы избежать последовательных и повторяющихся номеров):
N=10;
k=4;
increments = floor(rand(1,k)*(N-2))+2 %// increments allowed are from 2 to N-1 inclusive
out = mod(cumsum(increments), N)+1 %// sum increments
То же самое в python:
from numpy import cumsum, floor, mod, random
N=5
k=100
increments = floor(random.rand(1,k)*(N-2))+2
out = mod(cumsum(increments), N)+1
print(out)
[ 5. 3. 1. 5. 2. 4. 3. 2. 4. 2. 4. 3. 1. 5. 4. 3. 5. 4.
2. 5. 4. 2. 5. 2. 4. 1. 5. 4. 1. 5. 3. 1. 3. 2. 4. 1.
5. 4. 1. 3. 5. 4. 3. 5. 2. 1. 3. 2. 4. 3. 1. 4. 2. 1.
3. 2. 1. 4. 3. 2. 1. 3. 5. 3. 5. 4. 2. 4. 2. 1. 3. 2.
1. 3. 5. 2. 5. 4. 3. 1. 4. 1. 4. 3. 5. 4. 2. 1. 5. 2.
1. 5. 4. 2. 4. 3. 5. 2. 4. 1.]
Более 100 итераций, даже если я ограничу число до 1..5, нет повторного/последовательного числа.
Решение в MATLAB (возможно, неэлегантное) может быть примерно таким:
N = 10;
k = 4;
out = zeros(1,k);
vec = 1 : N;
for idx = 1 : k
ind = randi(numel(vec), 1);
left = max(ind-1, 1); right = min(numel(vec), ind+1);
out(idx) = vec(ind);
to_remove = ind;
if vec(left) == vec(ind)-1
to_remove = [to_remove left];
end
if vec(right) == vec(ind)+1
to_remove = [to_remove right];
end
vec(to_remove) = [];
end
Сначала объявляем N и k, затем объявляем выходной массив с нулями длиной k. Затем мы генерируем вектор выборки vec, который начинается от 1 до N. Затем, для каждого значения, которое мы хотим поместить в вывод, мы генерируем случайную позицию для выборки из вектора, затем смотрим на позицию слева и справа... обеспечивая, чтобы мы находились в пределах границ массив. Кроме того, мы только удаляем влево или вправо, если значение слева от индекса для удаления, а также справа равны друг другу (спасибо стакану!)
Мы используем это местоположение и образец из этого вектора, поместите значение в этом месте на выход, затем удалим индексы в этом векторе, которые находятся слева, справа, и фактический индекс из этого вектора. Это снова удалит возможность выборки из этих значений. Мы повторяем это до тех пор, пока не закончим значения для размещения на выходе.
Вот несколько пробных прогонов:
>> out
out =
9 7 1 5
>> out
out =
7 1 4 10
>> out
out =
10 8 1 6
>> out
out =
10 4 8 1
Иногда быстрее и проще создавать больше образцов, чем вам нужно, а затем отбрасывать нежелательные значения.
Один (медленный) пример.
vec= randi(100,1,1);
for j = 2:50,
while(abs(vec(j)-vec(j-1)<2) vec(j)= randi(100,1,1);end;
end
Другой способ. Предположим, вы хотите 50 образцов
vec = rand(100,100,1);
badindex = find(abs(vec(1:99)-vec(2:100) < 1));
vec(badindex) = vec(badindex-1)+vec(badindex+1);
% if you don't want big values,
vec(vec>100) = vec (vec>100) -100; % to ensure, I hope, that neighbors
% не являются последовательными
(Это было бы проще в R).
Не особенно элегантное решение python:
def nonseq(n, k):
out = [random.randint(0, n)]
while len(out) < k:
x = random.randint(0, n)
if abs(x - out[-1]) > 1:
out.append(x)
return out
Моя реализация:
def ncsample(population, k):
import random
if k > 0:
i = random.randrange(0, len(population) - 2*(k-1))
return [population[i]] + ncsample(population[i+2:], k-1)
else:
return []
Примечание: он случайным образом находит последовательность в одном кадре (без отбраковки в цикле while).
Реализация MATLAB:
function r = ncsample(population, k)
if k > 0
i = randi(length(population) - 2*(k-1));
r = [population(i) ncsample(population((i+2):end), k-1)];
else
r = [];
end
end
Некоторые тесты:
>> for i=1:10; fprintf('%s\n',sprintf('%d ', ncsample(1:10, 4))); end
1 5 7 9
3 5 8 10
3 5 8 10
4 6 8 10
2 6 8 10
1 4 8 10
1 4 7 9
3 6 8 10
1 6 8 10
2 4 7 9
Это рекурсивная элегантная версия, я просто добавил проверку на k и N, чтобы избежать бесконечной рекурсии, если k > N/2 не существует никакого решения.
Результат гарантируется случайным.
import random
def myFunc(N,k):
if k>(N+1)/2:
return "k to big for N"
returnValue = sorted(random.sample(range(1,N+1),k))
toTest = [x - returnValue[i - 1] for i, x in enumerate(returnValue)][1:]
if 1 in toTest:
return myFunc(N,k)
else:
return returnValue
print myFunc(10,4)