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

Question

给定一个有n个元素的集合，我需要找到所有将该集合划分为k个几乎相等大小子集的划分。

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

换句话说，对于一个有7个元素的集合，有877种可能的划分，但我只对由2/2/3个元素组成的105(?)个划分感兴趣。

                               

实际上，n大约为35，这意味着大约有2.81 * 10²⁷个分区，“仅有”8,338,573,669,964,101个具有三个子集的分区。因此，我不可能计算出所有的分区并找到我想要的那些。

“如何计算只有感兴趣的分区的算法？”（不是分区的数量，而是每个分区中每个子集的实际成员）。

- Phrogz

---

那么，“几乎相等大小的子集”是指每个子集之间的大小差异不能超过1？ - user456814

k有任何限制吗？您想要所有不同基数相差最多1的k个子集的所有分区吗？ - Fred

@Cupcake 正确。基本上，size，number_of_subsets_with_extra = n.divmod(k)。 - Phrogz

@Phrogz 你最初是想使用n的二进制表示生成一组n个元素的组合吗？ - user456814

我现在没有时间解释算法，但我们在Sage中有一个实现（请参见this file中的SetPartitions._iterator_part方法）。 - hivert

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!

- Marc-André Lafortune

---

很高兴知道计算 n = 35, k = 3 的所有可能性可能不值得 :P 我们能否使用这个来枚举子集呢？我必须说 Enumerator#size 对我来说有点奇怪。 - Niklas B.

发布修改后的代码以执行实际枚举，因为这是要求的。我保留了懒惰计算，因为我觉得它很可爱。 - Marc-André Lafortune

你认为通过跳过子集大小小于某个特定值的分区或跳过具有足够大数量子集的分区，可以加快代码速度吗？ - jokoon

Answer 2

重要观察：在分区大小不能相差超过1的条件下，分区大小的多重集合是唯一确定的。我们有 (n % k) 个大小为 ceil(n / k) 的部分和 (k - n % k) 个大小为 floor(n / k) 的分区。

因此，让我们固定分区大小，并枚举所有可能的子集以及所有分区：

@n = n = 7
@k = k = 3
@used = n.times.map { false }
#  @sizes = [2,2,3]  for n = 7, k = 3
@sizes = (k - n % k).times.map { n / k } + (n % k).times.map { (n + k - 1) / k }
@parts = @sizes.map { |i| [0]*i }
def enumerate_part(i, j, lo, y)
  # i = index of the current part
  # j = index of the current number in the current part
  # lo = lower bound for numbers to chose
  # y = output yielder
  if i == @parts.size
    y << @parts.map(&:dup)
    return
  end
  if j == @sizes[i]
    enumerate_part(i + 1, 0, @sizes[i + 1] == @sizes[i] ? @parts[i][0] : 1, y)
    return
  end
  (lo..@n).each do |x|
    next if @used[x]
    @used[x] = true
    @parts[i][j] = x
    enumerate_part(i, j + 1, x + 1, y)
    @used[x] = false
  end
end

results = Enumerator.new { |y| enumerate_part(0,0,1,y) }
puts results.count

请注意，对于大小相等的分区，我会分配递增的最小值以实现唯一性。这可能会导致一些回溯（最多2级），因此不是最优解。我们可能希望避免在我们已经知道下限将超出下一个同样大小的分区时分配数字。此时变得有点复杂，所以我保持了简单。肯定可以改进。

它只使用 O(n) 的空间，因为我改变全局状态而不是复制东西（是的，我向枚举器产生防御性副本，但如果您在每个迭代中立即处理结果，则不需要这样做）。也许不是最优雅的解决方案，但目标是实现良好的速度。

输出：

105

当 n （大于20）较大时，运行起来并不好玩。我觉得这是 Ruby 的问题，但幸运的是，这个特定的实现在几乎任何其他语言中看起来都很相似。

更新：只是为了好玩，我改进了算法，使其完全呈线性输出大小（除了维护剩余数字集合可能需要乘以n因子的情况）。这样应该会快几倍：

def dfs(i, j, lo, eq, sz, state)
  parts, y, n, k, left = state
  if i == k
    y << parts
    return
  end
  if j == sz
    mid = i+1 == n % k
    neweq, newsz = mid ? [k - i - 1, sz-1] : [eq - 1, sz]
    dfs(i+1, 0, mid ? 1 : parts[i][0], neweq, newsz, state)
    return
  end
  higher = ((j == 0) ? (eq * sz - j - 1) : (sz - j - 1))
  left.drop(higher).each_with_index do |x,idx|
    break if x < lo
    parts[i][j] = x
    left.delete_at(idx + higher)
    dfs(i, j + 1, x + 1, eq, sz, state)
    left.insert(idx + higher, x)
  end
end

def niklas(n, k)
  parts = k.times.map{|i| [0]*(i < n%k ? (n+k-1)/k : n/k) }
  left = n.downto(1).to_a
  results = Enumerator.new { |y|
    dfs(0, 0, 1, (n % k == 0) ? k : n % k, (n + k - 1) / k, [parts, y, n, k, left])
  }
  cnt = results.count
  puts "count = #{cnt} != #{@sz}" unless cnt == @sz
end

- Niklas B.

Answer 3

我相信这个解决方案（在基准测试中称为“cary1”）将完成工作：

代码

require 'set'

def doit(items, subs, so_far=[], combos=Set.new)
  return combos << (so_far+[items]).to_set if subs.size == 1
  items.combination(subs.first){|c|doit(items-c,subs[1..-1],so_far+[c],combos)}
  combos
end

演示

doit([1,2,3,4,5], [2,3]).to_a.map(&:to_a) # 10 combinations
  #=> [[[1, 2], [3, 4, 5]],   [[1, 3], [2, 4, 5]],   [[1, 4], [2, 3, 5]],
  #    [[1, 5], [2, 3, 4]],   [[2, 3], [1, 4, 5]],   [[2, 4], [1, 3, 5]],
  #    [[2, 5], [1, 3, 4]],   [[3, 4], [1, 2, 5]],   [[3, 5], [1, 2, 4]],
  #    [[4, 5], [1, 2, 3]]] 

doit([1,2,3,4,5], [2,1,2]).to_a.map(&:to_a) # 15 combinations
  #=> [[[1, 2], [3], [4, 5]],   [[1, 2], [4], [3, 5]],   [[1, 2], [5], [3, 4]],
  #    [[1, 3], [2], [4, 5]],   [[1, 3], [4], [2, 5]],   [[1, 3], [5], [2, 4]],
  #    [[1, 4], [2], [3, 5]],   [[1, 4], [3], [2, 5]],   [[1, 4], [5], [2, 3]],
  #    [[1, 5], [2], [3, 4]],   [[1, 5], [3], [2, 4]],   [[1, 5], [4], [2, 3]],
  #    [[2, 3], [1], [4, 5]],   [[2, 4], [1], [3, 5]],   [[2, 5], [1], [3, 4]]] 

doit([1,2,3,4,5,6,7], [2,2,3]).to_a.map(&:to_a) # 105 combinations
  # => [[[1, 2], [3, 4], [5, 6, 7]],   [[1, 2], [3, 5], [4, 6, 7]],
  #     [[1, 2], [3, 6], [4, 5, 7]],   [[1, 2], [3, 7], [4, 5, 6]],
  #     [[1, 2], [4, 5], [3, 6, 7]],   [[1, 2], [4, 6], [3, 5, 7]],
  #     ...
  #     [[4, 5], [6, 7], [1, 2, 3]],   [[4, 6], [5, 7], [1, 2, 3]],
  #     [[4, 7], [5, 6], [1, 2, 3]]] 

解释

• 我将数组subs视为给定的，因为构建subs似乎是一个单独且不是很困难的问题。
• 为了避免[[1],[2,3],[4]]和[[4],[2,3],[1]]同时包含在结果中，我将它们都转换成集合。当尝试将它们添加到结果集合时，只会添加第一个。我使用集合，因为没有提到给定集合的元素，特别是每对是否可以用<=>进行比较。根据结果的使用方式，将结果保留为一组集合可能已经足够。或者，集合可以很容易地转换为数组，就像我在“演示”部分所做的那样。

如果在调用doit之前未给出doit()中的subs，则可以像这样创建它：

def divide_up(items, k)
  m, r = items.size.divmod(k)
  puts "m = #{m}, r = #{r}"
  doit(items, Array.new(k-r, m) + Array.new(r, m+1))
end  

编辑：我做了一个小改动，使方法返回一组集合，认为这些可能可以直接使用。如果不行，它们可以很容易地转换为数组，就像我在演示部分所做的那样。

- Cary Swoveland

Answer 4

这里提供一种避免了我第一个解决方案中不必要的枚举的方法。这个解决方案在基准测试中被称为“cary2”。 代码

def doit(list, group_sizes)
  @group_sizes = group_sizes
  @combos = []
  @empty_group_filled_by_size = group_sizes.uniq.product([false]).to_h
  recurse(list, group_sizes.map { |sub| [] })
  @combos
end

def recurse(remaining_items_to_assign, assigned_so_far)
  empty_group_filled_by_size = @empty_group_filled_by_size.dup
  assigned_so_far.each_with_index do |group, ndx|
    next if group.size == @group_sizes[ndx] # all positions in group allocated
    if group.empty?
      group_size = @group_sizes[ndx]
      empty_group_filled_by_size[group_size] ? next :
        empty_group_filled_by_size[group_size] = true
    end
    assigned_so_far[ndx] << remaining_items_to_assign.first
    if remaining_items_to_assign.size == 1
      @combos << assigned_so_far.map { |group| group.dup } # deep copy
    else
      recurse(remaining_items_to_assign[1..-1], assigned_so_far)
    end
    assigned_so_far[ndx].pop
  end
end

Explanation

假设我们有12个项目要分配到三个大小为2的容器（B2a，B2b和B2c）和两个大小为3的容器（B3a和B3b）中。项目按顺序分配到容器中。 第一个项目可以分配到大小为2的容器之一（比如B2a），也可以分配到大小为3的容器之一（比如B3a）。它不能按顺序分配到每个给定大小的空容器中，因为那会导致重复计数。对于每个被分配到容器中的项目，使用数组empty_group_filled_by_size来跟踪该项目是否已经被分配到特定大小的第一个空容器中。 第二个项目的分配可能取决于项目1分配给哪个容器。如果项目1已分配到B2a，则项目2可以分配到B2a，分配到另外两个（仍为空的）大小为2的容器之一（比如B2b），或者分配到两个（空的）大小为3的容器之一（比如B3a）。如果项目1已分配到B3a，则项目2可以分配到任意一个大小为2的容器之一（比如B2a），分配到B3a或B3b。 这些分配将继续，直到只剩下一个要分配的项目，在此时只有一个容器不满，并且只有空间容纳一个项目。在将项目分配到容器中并将其保存在一个数组（@combos）中之后，递归回溯以考虑其他可能性。

- Cary Swoveland

Answer 5

我认为对三种已经贡献的解决方案进行基准测试可能会很有趣。如果有人想看到更多的测试，请告诉我，我会添加它们。

Niklas1

def enumerate_part(i, j, lo, y)
  # i = index of the current part
  # j = index of the current number in the current part
  # lo = lower bound for numbers to chose
  # y = output yielder
  if i == @parts.size
    y << @parts.map(&:dup)
    return
  end
  if j == @sizes[i]
    enumerate_part(i + 1, 0, @sizes[i + 1] == @sizes[i] ? @parts[i][0] : 1, y)
    return
  end
  (lo..@n).each do |x|
    next if @used[x]
    @used[x] = true
    @parts[i][j] = x
    enumerate_part(i, j + 1, x + 1, y)
    @used[x] = false
  end
end

def niklas1(n, k)
  @n, @k = n, k
  @used = n.times.map { false }
  #  @sizes = [2,2,3]  for n = 7, k = 3
  @sizes = (k - n % k).times.map { n / k } + (n % k).times.map { (n + k - 1) / k }
  @parts = @sizes.map { |i| [0]*i }
  results = Enumerator.new { |y| enumerate_part(0,0,1,y) }
  cnt = results.count
  puts "count = #{cnt} != #{@sz}" unless cnt == @sz   
end

Niklas2

def dfs(i, j, lo, eq, sz, state)
  parts, y, n, k, left = state
  if i == k
    y << parts
    return
  end
  if j == sz
    mid = i+1 == n % k
    neweq, newsz = mid ? [k - i - 1, sz-1] : [eq - 1, sz]
    dfs(i+1, 0, mid ? 1 : parts[i][0], neweq, newsz, state)
    return
  end
  higher = ((j == 0) ? (eq * sz - j - 1) : (sz - j - 1))
  left.drop(higher).each_with_index do |x,idx|
    break if x < lo
    parts[i][j] = x
    left.delete_at(idx + higher)
    dfs(i, j + 1, x + 1, eq, sz, state)
    left.insert(idx + higher, x)
  end
end

def niklas2(n, k)
  parts = k.times.map{|i| [0]*(i < n%k ? (n+k-1)/k : n/k) }
  left = n.downto(1).to_a
  results = Enumerator.new { |y|
    dfs(0, 0, 1, (n % k == 0) ? k : n % k, (n + k - 1) / k, [parts, y, n, k, left])
  }
  cnt = results.count
  puts "count = #{cnt} != #{@sz}" unless cnt == @sz
end

马克-安德烈

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

def marc_andre(n, k)
  a = enum(n, k).to_a
  a.size
end

Cary1

require 'set'

def cary1(n, k)
  m, r = n.divmod(k)
  cnt = doit([*1..n], Array.new(k-r, m) + Array.new(r, m+1)).to_a.map(&:to_a).size
  puts "count = #{cnt} != #{@sz}" unless cnt == @sz 
end

def doit(items, subs, so_far=[], combos=Set.new)
  return combos << (so_far+[items]).to_set if subs.size == 1
  items.combination(subs.first){|c|doit(items-c,subs[1..-1],so_far+[c],combos)}
  combos
end

Cary2

def cary2(n, k)
  m, r = n.divmod(k)
  cnt = doit2([*1..n], Array.new(k-r, m) + Array.new(r, m+1)).to_a.map(&:to_a).size
  puts "count = #{cnt} != #{@sz}" unless cnt == @sz 
end

def doit2(list, group_sizes)
  @group_sizes = group_sizes
  @combos = []
  @empty_group_filled_by_size = group_sizes.uniq.product([false]).to_h
  recurse(list, group_sizes.map { |sub| [] })
  @combos
end

def recurse(remaining_items_to_assign, so_far)
  empty_group_filled_by_size = @empty_group_filled_by_size.dup
  so_far.each_with_index do |group, ndx|
    next if group.size == @group_sizes[ndx] # all positions in group allocated
    if group.empty?
      group_size = @group_sizes[ndx]
      empty_group_filled_by_size[group_size] ? next :
        empty_group_filled_by_size[group_size] = true
    end
    so_far[ndx] << remaining_items_to_assign.first
    if remaining_items_to_assign.size == 1
      @combos << so_far.map { |group| group.dup } # deep copy
    else
      recurse(remaining_items_to_assign[1..-1], so_far)
    end
    so_far[ndx].pop
  end
end  

基准测试代码

require 'benchmark'

def bench_it(n, k, iterations)
  puts "\nn = #{n}, k = #{k}, size = #{@sz = marc_andre(n,k)}\n" 
  Benchmark.bm(%w[Niklas Marc-André Cary].map(&:size).max) do |bm|

    bm.report('Niklas1') do
      iterations.times do
        niklas1(n, k)
      end
    end

    bm.report('Niklas2') do
     iterations.times do
       niklas2(n, k)
     end
    end

    bm.report('Marc-André') do
      iterations.times do
        marc_andre(n, k)
      end
    end

    bm.report('Cary1') do
      iterations.times do
        cary1(n, k)
      end
    end

    bm.report('Cary2') do
      iterations.times do
        cary2(n, k)
      end
    end
  end
end

iterations = 1
bench_it( 7, 3, iterations)
bench_it(10, 2, iterations)
bench_it(10, 3, iterations)
bench_it(10, 4, iterations)
bench_it(13, 2, iterations)
bench_it(13, 3, iterations)
bench_it(13, 4, iterations)
bench_it(13, 5, iterations)
bench_it(16, 2, iterations)
bench_it(16, 3, iterations)
bench_it(16, 4, iterations)
bench_it(18, 2, iterations)
bench_it(18, 3, iterations)
bench_it(20, 2, iterations)

结果

建议在背景播放这个视频的情况下查看结果。

n = 7, k = 3, size = 105
                 user     system      total        real
Niklas1      0.000000   0.000000   0.000000 (  0.001131)
Niklas2      0.000000   0.000000   0.000000 (  0.000595)
Marc-André   0.000000   0.000000   0.000000 (  0.000911)
Cary1        0.000000   0.000000   0.000000 (  0.003241)
Cary2        0.000000   0.000000   0.000000 (  0.000922)

n = 10, k = 2, size = 126
                 user     system      total        real
Niklas1      0.010000   0.000000   0.010000 (  0.004986)
Niklas2      0.000000   0.000000   0.000000 (  0.001031)
Marc-André   0.000000   0.000000   0.000000 (  0.000880)
Cary1        0.000000   0.000000   0.000000 (  0.003850)
Cary2        0.000000   0.000000   0.000000 (  0.001607)

n = 10, k = 3, size = 2100
                 user     system      total        real
Niklas1      0.040000   0.000000   0.040000 (  0.042930)
Niklas2      0.010000   0.000000   0.010000 (  0.012296)
Marc-André   0.020000   0.000000   0.020000 (  0.017632)
Cary1        0.080000   0.000000   0.080000 (  0.081082)
Cary2        0.020000   0.000000   0.020000 (  0.018739)

n = 10, k = 4, size = 6300
                 user     system      total        real
Niklas1      0.090000   0.000000   0.090000 (  0.094029)
Niklas2      0.030000   0.000000   0.030000 (  0.030908)
Marc-André   0.040000   0.000000   0.040000 (  0.038247)
Cary1        0.510000   0.000000   0.510000 (  0.512819)
Cary2        0.060000   0.000000   0.060000 (  0.059061)

n = 13, k = 2, size = 1716
                 user     system      total        real
Niklas1      0.210000   0.000000   0.210000 (  0.219898)
Niklas2      0.020000   0.000000   0.020000 (  0.017828)
Marc-André   0.020000   0.000000   0.020000 (  0.015917)
Cary1        0.030000   0.000000   0.030000 (  0.029272)
Cary2        0.020000   0.000000   0.020000 (  0.022058)

n = 13, k = 3, size = 45045
                 user     system      total        real
Niklas1      1.480000   0.010000   1.490000 (  1.484895)
Niklas2      0.350000   0.000000   0.350000 (  0.343872)
Marc-André   0.470000   0.010000   0.480000 (  0.493646)
Cary1        1.890000   0.010000   1.900000 (  1.895684)
Cary2        0.520000   0.010000   0.530000 (  0.531843)

n = 13, k = 4, size = 200200
                 user     system      total        real
Niklas1      4.160000   0.070000   4.230000 (  4.225072)
Niklas2      1.210000   0.000000   1.210000 (  1.216814)
Marc-André   2.170000   0.030000   2.200000 (  2.203629)
Cary1       29.930000   0.580000  30.510000 ( 30.545276)
Cary2        1.720000   0.040000   1.760000 (  1.757895)

n = 13, k = 5, size = 600600
                 user     system      total        real
Niklas1     12.750000   0.040000  12.790000 ( 12.800083)
Niklas2      3.070000   0.010000   3.080000 (  3.085927)
Marc-André   3.630000   0.010000   3.640000 (  3.637411)
Cary1      191.200000   0.890000 192.090000 (192.319270)
Cary2        5.290000   0.300000   5.590000 (  5.625138)

n = 16, k = 2, size = 6435
                 user     system      total        real
Niklas1      2.120000   0.010000   2.130000 (  2.131065)
Niklas2      0.090000   0.010000   0.100000 (  0.092635)
Marc-André   0.080000   0.000000   0.080000 (  0.076312)
Cary1        0.290000   0.000000   0.290000 (  0.295062)
Cary2        0.070000   0.000000   0.070000 (  0.071995)

n = 16, k = 3, size = 1009008
                 user     system      total        real
Niklas1     62.370000   0.940000  63.310000 ( 63.404404)
Niklas2      8.070000   0.020000   8.090000 (  8.099837)
Marc-André  14.080000   0.330000  14.410000 ( 14.424437)
Cary1       48.930000   0.220000  49.150000 ( 49.227445)
Cary2       13.540000   0.280000  13.820000 ( 13.856880)

n = 16, k = 4, size = 2627625
                 user     system      total        real
Niklas2     22.530000   0.290000  22.820000 ( 23.252738)
Marc-André  35.850000   1.160000  37.010000 ( 37.159520)
Cary2       39.850000   0.860000  40.710000 ( 40.780489)

n = 18, k = 2, size = 24310
                 user     system      total        real
Niklas2      0.280000   0.000000   0.280000 (  0.288286)
Marc-André   0.240000   0.020000   0.260000 (  0.262669)
Cary2        0.240000   0.010000   0.250000 (  0.245008)

n = 18, k = 3, size = 2858856
                 user     system      total        real
Niklas2     37.150000   2.670000  39.820000 ( 48.484321)
Marc-André  68.010000   1.350000  69.360000 ( 70.249403)
Cary2       48.300000   0.840000  49.140000 ( 49.591279)

n = 20, k = 2, size = 92378
                 user     system      total        real
Niklas2      1.260000   0.000000   1.260000 (  1.271094)
Marc-André   1.180000   0.040000   1.220000 (  1.205478)
Cary2        1.210000   0.010000   1.220000 (  1.232024)

解释

我们似乎已经有一个明显的胜者了。恭喜，Marc-André! Niklas，这次没有金牌，但银牌也不错。

我会让@Niklas和@Marc-André自己解释他们的代码，因为他们更了解它们的代码如何运作。当k的值很小(2或3)时，我的代码似乎运行得还不错。然而，随着这个参数的增加，我的代码花费越来越多的时间去除重复 (例如，当我已经“拥有”[[6,7,[3,4,5][2,3]]]时，忽略了[[2,3],[3,4,5],[6,7])。特别是，看一下n=13，k=5的结果。这部分是因为我设计的代码适用于任意的分区，而不仅仅是像[m,m,...,m,m+1,m+1,...m+1]这样的分区。我将检查是否有什么方法可以利用这种结构(不会彻底改变我的代码)，但我对结果并不乐观。

编辑

我已更新基准测试，包括我的第二个解决方案（“cary2”）的结果。它发布的解决方案时间大致与@Marc-André 的相当，这并不奇怪，因为两个算法都避免了不必要的组合枚举。

编辑 2

我已更新基准测试，包括 @Niklas 的第二个解决方案。我将新的标记为“Niklas2”，原始的标记为“Nicklas1”。 我还添加了两个测试用例 n = 18。我尝试运行 n = 20, k = 3（对于“Niklas1”，“Marc-André”和“Cary2”），但在大约5分钟后取消了，因为它没有获得初始解。

我相信结果说明了问题。

- Cary Swoveland

---

@Marc-André。我修改了你的代码并重新运行了基准测试。请确认这些更改是否正确。 - Cary Swoveland

我已经将我的C++版本与算法改进翻译成了Ruby，现在应该会快得多（对于大实例来说快了约10倍，比Marc的快了约2倍）。@Marc-AndréLafortune 这并不是一个真正的论点，这里所有的算法都具有这个特性。不过，接受挑战 :P - Niklas B.

@Marc-AndréLafortune，您的方法非常优雅。在解释型语言中实现良好速度的关键是充分利用标准库。 - Niklas B.

@NiklasB。我的意思是，大多数其他算法循环比我的多，使用集合或使用“next”修剪可能性。 - Marc-André Lafortune

@Niklas，我已经更新了基准测试，包括您最新的产品。 - Cary Swoveland