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

Question

给定一个包含 n 个元素的集合，我需要找到该集合的所有分区，其中有 k 个大小几乎相等的子集。

例如，对于一个有 7 个元素和 3 个子集的集合，我只想要分区，其中有两个子集，每个子​​集有 2 个元素，一个子集有 3 个元素。我不想要一个包含 1、2 和 4 个元素的子集的分区。

换句话说，有877 possible partitions对于一组 7 个元素，但我只对由 2/2/3 个元素组成的子集组成的 105 个(？)分区感兴趣:

实际上 n 大约是 35，这意味着大约有 2.81 * 10²⁷ 个分区，“仅”8,338,573,669,964,101 partitions with three subsets .因此，我不可能将它们全部计算出来并费力地找到我想要的。

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

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!