Как многократно добавлять случайные значения в пустой вектор, не зная, когда он остановится?Как посчитать среднее количество шагов?

Question

Представьте себе процесс формирования вектора v, начиная с пустого вектора, а затем многократно помещая случайно выбранное число от 1 до 20 в конце v. Как вы могли бы использовать Matlab, чтобы в среднем выяснить, сколько шагов нужно сделать, чтобы v содержал все числа от 1 до 20? Вы можете определить / использовать столько функций или скриптов, сколько хотите в своем ответе.

v=[];
v=zeros(1,20);

for a = 1:length(v)
  v(a)=randi(20);
end

, поскольку v теперь является вектором 1x20, если равны два числа, это определенно не имеет все 20 чисел от 1 до 20

for i = 1:length(v)
  for j = i+1:length(v)
    if v(i)==v(j) 
      v=[v randi(20)];
      i=i+1;
      break;
    end
  end
end



for k = 1:length(v)
  for n = 1:20
    if v(k)==n
      v=v;
    elseif v(k)~=n
      a=randi(20);
      v=[v a];
    end
    if a~=n
      v=[v randi(20)];
      k=k+1;
      break;
    end
  end
end

disp('number of steps: ')
i*k

Answer 1

Прежде всего, цикл, генерирующий вектор, должен быть бесконечным. Вы можете выйти из цикла, если ваше условие выполнено. Вот как вы можете посчитать, сколько шагов вам нужно. Вы не можете использовать цикл более 20 шагов, если вы знаете, что вам нужно больше, чем это. Мне нравится использовать while true и break.

Далее, ваш метод определения наличия всех элементов - это метод O (n ² ). Это может быть сделано в O (n log n) сортировке элементов. Это то, что делает unique. Он работает путем сортировки, которая, в общем случае, O (n log n) (подумайте QuickSort). Итак, рисование n элементов и после каждой проверки, чтобы увидеть, все ли у вас есть, является операцией O (n ² log n). Это дорого!

Но мы говорим о конечном наборе целых чисел здесь. Целые числа могут быть отсортированы в O (n) (ищите сортировку гистограммы или сортировку по основанию). Но мы можем сделать еще лучше, потому что нам даже не нужно физически создавать вектор или сортировать его значения. Вместо этого мы можем просто отслеживать элементы, которые мы видели в массиве длиной 20: в цикле сгенерировать следующий элемент вектора, установить соответствующее значение в вашем массиве из 20 элементов, и когда все элементы этого массива установлены, Вы видели все значения хотя бы один раз. Это когда ты ломаешься.

Моя реализация этих двух методов приведена ниже. Для метода unique требуется 11 с, чтобы выполнить 10000 повторений этого процесса, а для другого - всего 0,37 с. После 10 000 повторений я увидел, что вам нужно в среднем около 72 шагов, чтобы увидеть все 20 целых чисел.

function test

k = 10000;

tic;
n1 = 0;
for ii=1:k
   n1 = n1 + method1;
end
n1 = n1 / k;
toc
disp(n1)

tic;
n2 = 0;
for ii=1:k
   n2 = n2 + method2;
end
n2 = n2 / k;
toc
disp(n2)

end

function n = method1
k = 20;
v = [];
n = 1;
while true
   v(end+1) = randi(k);
   if numel(unique(v))==k
      break;
   end
   n = n + 1;
end
end

function n = method2
k = 20;
h = zeros(20,1);
n = 1;
while true
   h(randi(k)) = 1;
   if all(h)
      break;
   end
   n = n + 1;
end
end

Примечание по времени: я использую tic / toc здесь, но обычно лучше использовать timeit вместо этого. Разница во времени достаточно велика, чтобы это не имело большого значения. Но убедитесь, что код, который использует tic / toc, находится внутри функции и не вставляется в командную строку. Времена не являются репрезентативными при использовании tic / toc в командной строке, потому что компилятор JIT не будет использоваться.

Answer 2

Я не уверен, правильно ли я понимаю ваш вопрос, но, возможно, взгляните на функцию unique().

если

length(unique(v)) == 20 

тогда у вас есть все значения от 1:20 в вашем векторе

v = []
counter = 0;
while length(unique(v)) ~= 20
    a = randi(20);
    v=[v a];
    counter = counter +1
end

значение counter должно дать вам количество необходимых итераций, пока v не содержит все значения.

Если вы хотите получить среднее количество итераций методом проб и ошибок, просто посмотрите вокруг этого кода, протестируйте его 10000 раз и усредните результаты в форме counter.