枚举分布 [英] Enumerating distibutions

问题描述

我正在尝试创建一个文本文件，每一种可能的分布都将100％分布到n个容器中?这样，对于4个容器，它将看起来像这样:

I'm trying to create a text file with every possible distribution of 100% into n containers? So that for 4 containers, it would look something like this:

0.97, 0.01, 0.01, 0.01  
0.96, 0.01, 0.01, 0.02  
0.96, 0.01, 0.02, 0.01  
0.96, 0.02, 0.01, 0.01
...  

有什么好的方法可以实现这一目标吗?

Any ideas on a good way to accomplish this?

推荐答案

根据您在上面评论中的回答，以下是Ruby中的递归解决方案:

Based on your response in the comments above, here's a recursive solution in Ruby:

$resolution = 100
$res_f = $resolution.to_f

def allocate(remainder, bin_number, all_bin_values, number_of_bins)
  if bin_number >= number_of_bins
    all_bin_values << remainder / $res_f
    puts all_bin_values.join(", ")
    all_bin_values.pop
  else
    remainder.downto(1) do |i|
      if remainder - i >= number_of_bins - bin_number
        all_bin_values << i / $res_f
        allocate(remainder - i, bin_number + 1, all_bin_values, number_of_bins)
        all_bin_values.pop
      end
    end
  end
end

num_bins = (ARGV.shift || 4).to_i
allocate($resolution, 1, [], num_bins)

容器的数量默认为4，但是您可以在运行时通过提供命令行参数来覆盖它.

The number of containers defaults to 4, but you can override that at run time by providing a command-line argument.

附录

您对循环版本太慢"的评论感到惊讶.在所有其他条件都相同的情况下，循环应该比递归更快，这就是我为此处给出的迭代版本计时的情况:

I was surprised by your comment that a looped version "was way too slow". All else being equal, looping should be faster than recursion and that was the case when I timed the iterative version given here:

resolution = 100
res_f = resolution.to_f

resolution.downto(1) do |first|
  remainder1 = resolution - first
  remainder1.downto(1) do |second|
    remainder2 = remainder1 - second
    remainder2.downto(1) do |third|
      fourth = remainder2 - third
      printf "%g, %g, %g, %g\n", first / res_f,
        second / res_f, third / res_f, fourth / res_f if fourth > 0
    end
  end
end

尽管这样做速度更快，但缺点是，如果您想要不同数量的容器，则必须通过添加其他嵌套循环来相应地修改代码.

Although this is faster, the downside is that if you wanted a different number of containers the code would have to be modified accordingly by adding additional nested loops.

这篇关于枚举分布的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！