计算具有特定子集大小的集合分区

Question

给定一个具有n个元素的集合,我需要找到该集合中具有几乎相等大小的k个子集的所有分区.

例如,对于具有7个元素和3个子集的集合,我只需要分区,其中有两个子集,每个子​​集有2个元素,一个子集有3个元素.我不希望分区具有1,2和4个元素的子集.

换句话说,一组7个元素有877个可能的分区,但我只对105(？)分区感兴趣,这些分区由2/2/3个元素构成子集:

                               

实际上,n大约为35,这意味着大约有2.81*10 ^27个分区,"仅" 8,338,573,669,964,101个分区有三个子集.因此,我不可能全部计算它们并趟过去找到我想要的那些.

什么算法只计算感兴趣的分区？(不是分区数,而是每个分区的每个子集中的实际成员.)

Answer 1

这是一个很好的方法，通过保持排序来仅生成所有可能性一次，以及一种快速计算答案数量的方法：

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

注意：只是为了好玩，这也可以通过构建一些枚举器并使用来延迟计算大小size，而不需要迭代它们。但这仅适用于 Ruby 2.0+，因为它需要Enumerator#size.

为了增加乐趣：

require 'with_progress'
enum(16, 3).with_progress.count # => enjoy!