给定一组n元素，我需要找到该集合的所有分区k大小几乎相等的子集。
例如，对于一个包含 7 个元素和 3 个子集的集合，我只需要其中有两个子集（每个子集包含 2 个元素）和一个子集包含 3 个元素的分区。我不想要一个包含 1、2 和 4 个元素子集的分区。
换句话说，有877个可能的分区 http://phrogz.net/svg/stirling_numbers.xhtml#s7对于一组 7 个元素，但我只对由 2/2/3 个元素组成的子集的 105 个（？）分区感兴趣：
In reality n is around 35, which means that there are approximately 2.81 * 1027 partitions, "only" 8,338,573,669,964,101 partitions with three subsets http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Definition. As such, I can't possibly calculate them all and wade through to find the ones that I want.
仅计算感兴趣的分区的算法是什么？（不是分区的数量，而是每个分区的每个子集中的实际成员。）
这是一个很好的方法，通过保持排序来仅生成所有可能性一次，以及一种快速计算答案数量的方法：
def enum(n, k)
# Pick smaller_size items from the list, repeat smaller_n times
# then pick larger_size items from the list, repeat larger_n times.
smaller_n = n.div k
larger_times = n % k
smaller_times = k - larger_times
larger_n = smaller_n + 1
return to_enum(:enum, n, k) { calc_size(n, smaller_n, smaller_times, larger_n, larger_times) } unless block_given?
all = [*1..n]
# split all into one subset to group with the smaller_n and another
# to group with the larger_n.
all.combination(smaller_n * smaller_times).each do |smaller|
larger = all - smaller
subdivide(smaller, smaller_n) do |small|
subdivide(larger, larger_n) do |large|
yield [*small, *large]
end
end
end
end
# Subdivides elems into groups of n, keeping the elements sorted
# and generating only the sorted such combinations.
def subdivide(elems, n)
return yield [] if elems.empty?
# No choice for the first element, because we want to keep things sorted.
first, *rest = elems
rest.combination(n - 1).each do |comb|
remain = rest - comb
subdivide(remain, n) do |sub|
yield [[first, *comb], *sub]
end
end
end
def calc_size(n, smaller_n, smaller_times, larger_n, larger_times)
all = [
smaller_times.times.map do |i|
Array.new(n - i*smaller_n).combination(smaller_n)
end,
larger_times.times.map do |i|
Array.new(n - smaller_times*smaller_n - i*larger_n).combination(larger_n)
end
]
# Multiply everything, but divide by the number of symmetries, because
# we don't want to distinguish (1,2), (3,4), ... from (3,4), (1,2), ...
all.map do |enums|
enums.map(&:size).inject(1, :*) / enums.permutation.size
end.inject(:*)
end
p enum(7, 3).size # => 105 (instant)
p enum(7, 3).first(5) # => [[[1, 2], [3, 4], [5, 6, 7]],
# [[1, 3], [2, 4], [5, 6, 7]],
# [[1, 4], [2, 3], [5, 6, 7]],
# [[1, 2], [3, 5], [4, 6, 7]],
# [[1, 3], [2, 5], [4, 6, 7]]]
p enum(7, 3).count # => 105 (quick)
p enum(35, 3).size # => 564121960420200 (instant)
p enum(35, 3).first(2) # => [[[1..11], [12..23], [24..35]],
# [[1..11], [12..22, 24], [23, 25..35]]]
p enum(35, 3).count # => will take forever, should return 564121960420200
Note：只是为了好玩，这也可以通过构建一些枚举器并使用来延迟计算大小size，无需迭代它们。不过，这仅适用于 Ruby 2.0+，因为它需要Enumerator#size http://ruby-doc.org/core-2.0/Enumerator.html#method-i-size.
为了增加乐趣：
require 'with_progress'
enum(16, 3).with_progress.count # => enjoy!