如何在不知道何时停止的情况下重复将随机值添加到空向量中？如何计算平均步数？

Question

想象一下形成一个向量v的过程，从空向量开始，然后在v的末尾重复放置从1到20的随机选择的数字。您如何使用 Matlab 调查在 v 包含从 1 到 20 的所有数字之前平均需要多少步？您可以 define/use 在答案中添加任意数量的函数或脚本。

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

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

因为v现在只是一个1x20的向量，如果有两个数相等，肯定没有从 1 到 20 的所有 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

我不确定我是否正确理解了你的问题，但也许可以看看 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。

Answer 2

首先，生成向量的循环必须是无限的。如果满足您的条件，您可以跳出循环。这就是您计算需要多少步数的方法。如果您知道自己需要的不止于此，则不能使用超过 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方法需要11s来重复这个过程10000次，而另一个只需要0.37s。重复 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 编译器。

如何在不知道何时停止的情况下重复将随机值添加到空向量中？如何计算平均步数？

How to add random values into an empty vector repeatedly without knowing when it would stop? How to count average number of steps?

matlab

random

montecarlo