ruby - 部分笛卡尔积(确保每组一个值)

Question

给定一组项目[z,a,b,c] 我想找到“笛卡尔幂”(笛卡尔积自身 n 次)但是 < strong>仅包含 z 的结果。例如:

normal_values = ["a","b","c"]
p limited_cartesian( normal_values, "z", 2 )
#=> [
#=>   ["z", "z"]
#=>   ["z", "a"]
#=>   ["z", "b"]
#=>   ["z", "c"]
#=>   ["a", "z"]
#=>   ["b", "z"]
#=>   ["c", "z"]
#=> ]

我可以通过旋转整个集合并跳过没有特殊值的条目来做到这一点，但我想知道是否有更简单的方法。最好是一个允许我懒惰地评估所需条目的方法，而不会浪费时间计算不需要的条目。

def limited_cartesian( values, special, power )
  [special, *values].repeated_permutation(power)
                    .select{ |prod| prod.include?( special ) }
end

Answer 1

编辑:有了 v3.0，我终于有了一些值得尊敬的东西。通常情况下，关键是以正确的方式看待问题。我突然想到我可以重复排列 normal_values << special , power - 1次，那么对于这些​​排列中的每一个，都会有一个元素要添加。如果排列至少包含一个 special , normal_values << special 的任意元素可以添加；否则，special必须添加。

def limited_cartesian( values, special, power )
  all_vals = values + [special]
  all_vals.repeated_permutation(power-1).map do |p|
    if p.include?(special)
      *all_vals.each_with_object([]) { |v,a| a << (p + [v]) }
    else
      p + [special]
    end
  end       
end

limited_cartesian( values, 'z', 1 )
  # [["z"]]

limited_cartesian( values, 'z', 2 )
  # => [["a", "z"], ["b", "z"], ["c", "z"],
  #     ["z", "a"], ["z", "b"], ["z", "c"],
  #     ["z", "z"]] 

limited_cartesian( values, 'z', 3 )
  # => [["a", "a", "z"], ["a", "b", "z"], ["a", "c", "z"],
  #     ["a", "z", "a"], ["a", "z", "b"], ["a", "z", "c"],
  #     ["a", "z", "z"], ["b", "a", "z"], ["b", "b", "z"],
  #     ["b", "c", "z"], ["b", "z", "a"], ["b", "z", "b"],
  #     ["b", "z", "c"], ["b", "z", "z"], ["c", "a", "z"],
  #     ["c", "b", "z"], ["c", "c", "z"], ["c", "z", "a"],
  #     ["c", "z", "b"], ["c", "z", "c"], ["c", "z", "z"],
  #     ["z", "a", "a"], ["z", "a", "b"], ["z", "a", "c"],
  #     ["z", "a", "z"], ["z", "b", "a"], ["z", "b", "b"],
  #     ["z", "b", "c"], ["z", "b", "z"], ["z", "c", "a"],
  #     ["z", "c", "b"], ["z", "c", "c"], ["z", "c", "z"],
  #     ["z", "z", "a"], ["z", "z", "b"], ["z", "z", "c"],
  #     ["z", "z", "z"]] 

这是我的 v2.1，可以工作，但不漂亮。我会把它留作记录。

def limited_cartesian( values, special, power )
  ndx = Array(0...power)
  ndx[1..-1].each_with_object( [[special]*power] ) do |i,a|
    ndx.combination(i).to_a.product(values.repeated_permutation(power-i).to_a)
       .each { |pos, val| a << stuff_special(special, pos, val.dup) }
  end
end

def stuff_special( special, pos, vals )
  pos.each_with_object(Array.new(pos.size + vals.size)) {|j,r|
    r[j] = special }.map {|e| e.nil? ? vals.shift : e }
end
  # e.g., stuff_special( 'z', [1,4], ["a","b","c"]) => ["a","z","b","c","z"]