如何判断数组是否为无重复组合？Ruby数组组合操作示例

针对你的需求，我整理了两种不同场景下的判断方案，分别对应Ruby内置Array#combination方法的严格输出，以及数学意义上的无重复组合判断：

场景1：严格匹配Ruby combination方法的结果（考虑元素顺序） #

Ruby的combination方法生成的子数组会保持原数组中元素的相对顺序，比如source.combination(2)不会生成[:b, :a]这样的数组。如果需要严格判断目标数组是否是该方法生成的有效组合，可以用以下实现：

source = [:a, :b, :c, :d, :e]

def valid_combination?(target, source)
  # 第一步：检查目标数组所有元素都属于原数组，且自身无重复
  return false unless (target - source).empty? && target.uniq == target
  
  # 第二步：检查目标数组的长度在合法范围内（1到原数组长度）
  k = target.size
  return false if k < 1 || k > source.size
  
  # 第三步：验证目标数组是否存在于combination(k)的结果中
  source.combination(k).include?(target)
end

# 测试示例
puts valid_combination?([:a], source)                # => true
puts valid_combination?([:a, :b], source)            # => true
puts valid_combination?([:b, :a], source)            # => false（不符合原数组元素顺序）
puts valid_combination?([:a, :f], source)            # => false（包含原数组外元素）
puts valid_combination?([:a, :a], source)            # => false（存在重复元素）
puts valid_combination?([:a, :b, :c, :d, :e], source) # => true

优化版本（适合大数组） #

如果原数组元素较多，生成所有组合会影响效率，我们可以通过验证元素在原数组中的索引是否严格递增来实现，无需生成全部组合：

source = [:a, :b, :c, :d, :e]
# 预先存储原数组元素的索引，提升查询效率
element_indices = source.each_with_index.to_h

def valid_combination_optimized?(target, element_indices)
  # 检查所有元素都存在于原数组，且自身无重复
  return false unless target.all? { |elem| element_indices.key?(elem) } && target.uniq.size == target.size
  
  # 检查元素在原数组中的索引严格递增（保证相对顺序符合combination的规则）
  prev_index = -1
  target.each do |elem|
    current_index = element_indices[elem]
    return false if current_index <= prev_index
    prev_index = current_index
  end
  
  # 检查长度合法
  target.size.between?(1, element_indices.size)
end

# 测试示例
puts valid_combination_optimized?([:a, :c], element_indices) # => true
puts valid_combination_optimized?([:c, :a], element_indices) # => false
puts valid_combination_optimized?([:b, :d, :e], element_indices) # => true

场景2：数学意义上的无重复组合（不考虑元素顺序） #

如果只需要判断目标数组是原数组的一个无重复子集（即数学概念中的组合，不关心元素顺序），可以通过集合来实现：

source = [:a, :b, :c, :d, :e]
source_set = source.to_set

def valid_combination_math?(target, source_set)
  target_set = target.to_set
  # 三个条件：目标数组无重复、目标是原数组的子集、长度在合法范围
  target.size == target_set.size && source_set.superset?(target_set) && target.size.between?(1, source_set.size)
end

# 测试示例
puts valid_combination_math?([:b, :a], source_set) # => true（数学上属于有效组合）
puts valid_combination_math?([:a, :b], source_set) # => true
puts valid_combination_math?([:a, :a], source_set) # => false（存在重复）
puts valid_combination_math?([:f], source_set)     # => false（元素不在原数组中）

内容的提问来源于stack exchange，提问作者anquegi