Enumerating distibutions

Question

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?

Answer 1

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)

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

ADDENDUM

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.