ruby - 如何从 n 个元素的数组中获取 'fair combination'？

Question

在 Ruby 上使用 combination 方法，

[1, 2, 3, 4, 5, 6].combination(2).to_a
#=> [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [2, 3],
#    [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6],
#    [4, 5], [4, 6], [5, 6]]

我们可以得到一个有 15 (6C2) 个元素的二维数组。

我想创建一个 fair_combination 方法来返回这样的数组:

arr = [[1, 2], [3, 5], [4, 6],
       [3, 4], [5, 1], [6, 2],
       [5, 6], [1, 3], [2, 4],
       [2, 3], [4, 5], [6, 1],
       [1, 4], [2, 5], [3, 6]]

因此每三个子数组(6 个子数组的一半)包含所有给定元素:

arr.each_slice(3).map { |a| a.flatten.sort }
#=> [[1, 2, 3, 4, 5, 6],
#    [1, 2, 3, 4, 5, 6],
#    [1, 2, 3, 4, 5, 6],
#    [1, 2, 3, 4, 5, 6],
#    [1, 2, 3, 4, 5, 6]]

随着数组的继续使用尽可能不同的元素，这使得它有点“公平”。

为了更通用，需要满足的条件如下:

(1) 当你从头开始跟随数组并计算每个数字出现的次数时，在任何时候它都应该尽可能平坦;

(1..7).to_a.fair_combination(3)
#=> [[1, 2, 3], [4, 5, 6], [7, 1, 4], [2, 5, 3], [6, 7, 2], ...]

前 7 个数字组成 [1,2,...,7]，接下来的 7 个数字也是如此。

(2) 一旦数字 A 与 B 在同一个数组中，如果可能，A 不想与 B 在同一个数组中。

(1..10).to_a.fair_combination(4)
#=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 1, 5], [2, 6, 9, 3], [4, 7, 10, 8], ...]

是否有任何好的算法可以创建这样的“公平组合”？

Answer 1

不能保证提供最佳解决方案，但可以提供足够好的解决方案。

在每一步，它都会选择一个最小子池，它是最小高度项目的集合，仍然有一个组合可供选择(高度是项目之前被使用的次数)。

例如，设枚举数为

my_enum = FairPermuter.new('abcdef'.chars, 4).each

第一次迭代可能会返回

my_enum.next  # => ['a', 'b', 'c', 'd']

此时这些字母的高度为 1，但是没有足够的高度为 0 的字母来进行组合，所以下一个只取所有字母:

my_enum.next  # => ['a', 'b', 'c', 'e'] for instance

现在 a、b 和 c 的高度为 2，1 对于 d 和 e，0 对于 f，最优池仍然是完整的初始集。

所以这并没有真正针对大尺寸的组合进行优化。另一方面，如果组合的大小最多为初始集大小的一半，则该算法相当不错。

class FairPermuter
  def initialize(pool, size)
    @pool = pool
    @size = size
    @all = Array(pool).combination(size)
    @used = []
    @counts = Hash.new(0)
    @max_count = 0
  end

  def find_valid_combination
    [*0..@max_count].each do |height|
      candidates = @pool.select { |item| @counts[item] <= height }
      next if candidates.size < @size
      cand_comb = [*candidates.combination(@size)] - @used
      comb = cand_comb.sample
      return comb if comb
    end
    nil
  end

  def each
    return enum_for(:each) unless block_given?
    while combination = find_valid_combination
      @used << combination
      combination.each { |k| @counts[k] += 1 }
      @max_count = @counts.values.max
      yield combination
      return if @used.size >= [*1..@pool.size].inject(1, :*)
    end
  end
end

4 比 6 的公平组合的结果

[[1, 2, 4, 6], [3, 4, 5, 6], [1, 2, 3, 5],
 [2, 4, 5, 6], [2, 3, 5, 6], [1, 3, 5, 6],
 [1, 2, 3, 4], [1, 3, 4, 6], [1, 2, 4, 5],
 [1, 2, 3, 6], [2, 3, 4, 6], [1, 2, 5, 6],
 [1, 3, 4, 5], [1, 4, 5, 6], [2, 3, 4, 5]]

2比6的公平组合结果

[[4, 6], [1, 3], [2, 5],
 [3, 5], [1, 4], [2, 6],
 [4, 5], [3, 6], [1, 2],
 [2, 3], [5, 6], [1, 6],
 [3, 4], [1, 5], [2, 4]]

2 比 5 的公平组合结果

[[4, 5], [2, 3], [3, 5],
 [1, 2], [1, 4], [1, 5],
 [2, 4], [3, 4], [1, 3],
 [2, 5]]

是时候得到 5 超过 12 的组合了:

        1.19 real         1.15 user         0.03 sys