arrays - 选择模式元素与规则匹配的数组排列

Question

给定一个包含五个元素的数组 ary:

ary = [true, true, true, false, false]

我想采用 ary 的所有排列，其中两个 false 值不连续，考虑到最后一个位置(索引 4 ) 环绕到第一个(索引 0):

[true, false, true, false, true] #=> Selected
[true, true, false, true, false] #=> Selected
[false, true, true, true, false] #=> Rejected

我认为答案可能归结为 select 和 each_with_index 方法。我不确定如何使用逻辑表达式关联数组中的元素。

Answer 1

这种递归方法直接生成排列，而不是生成大量排列并丢弃那些不满足规范的排列。

代码

def all_perms(arr_size, nbr_false)
  return nil if nbr_false > arr_size/2
  return [true]*arr_size if nbr_false.zero?
  recurse(arr_size, nbr_false, true)
end

def recurse(arr_size, nbr_false, full_arr)
  last_first = arr_size + 1 - 2*nbr_false
  (0..last_first).each_with_object([]) do |i,a|
    pre = [true]*i << false
    case nbr_false
    when 1
      a << pre + [true]*(arr_size-pre.size)
    else
      pre << true
      sub_arr_size = arr_size - pre.size - (i.zero? && full_arr ? 1 : 0)
      post = [true]*(arr_size-pre.size-sub_arr_size)
      recurse(sub_arr_size, nbr_false-1, false).each { |aa| a << pre + aa + post }
    end
  end
end

示例

arr_size  = 5
nbr_false = 2

b = all_perms(arr_size, nbr_false)
  #=> [[false, true, false, true, true],
  #    [false, true, true, false, true],
  #    [true, false, true, false, true],
  #    [true, false, true, true, false],
  #    [true, true, false, true, false]]
b == b.uniq
  #=> true
b.any? { |a| a.each_cons(2).any? { |x,y| x == false && y == false} }
  #=> false
b.any? { |a| a.first == false && a.last == false }
  #=> false

arr_size  = 8
nbr_false = 3

b = all_perms(arr_size, nbr_false)
  #=> [[false, true, false, true, false, true, true, true],
  #    [false, true, false, true, true, false, true, true],
  #    [false, true, false, true, true, true, false, true],
  #    [false, true, true, false, true, false, true, true],
  #    [false, true, true, false, true, true, false, true],
  #    [false, true, true, true, false, true, false, true],
  #    [true, false, true, false, true, false, true, true],
  #    [true, false, true, false, true, true, false, true],
  #    [true, false, true, false, true, true, true, false],
  #    [true, false, true, true, false, true, false, true],
  #    [true, false, true, true, false, true, true, false],
  #    [true, false, true, true, true, false, true, false],
  #    [true, true, false, true, false, true, false, true],
  #    [true, true, false, true, false, true, true, false],
  #    [true, true, false, true, true, false, true, false],
  #    [true, true, true, false, true, false, true, false]] 

b == b.uniq
  #=> true
b.any? { |a| a.each_cons(2).any? { |x,y| x == false && y == false} }
  #=> false
b.any? { |a| a.first == false && a.last == false }
  #=> false

注释

• 对于给定大小且包含相同数量 false 元素的所有数组，有效排列都是相同的。因此，我将 all_perms 的参数设置为所需数组的大小以及它要包含的 false 元素的数量(其他元素均为 true) >).
• recurse 的第三个参数 full_arr 是一个 bool 值，当调用 recurse 时，该值等于 true all_perms 但当从 recurse 调用 recurse 时等于 false。这是为了避免以 false 开头和结尾的排列(要避免的循环条件)所必需的。当 full_arr 为 true 且 i #=> 0 时，正在构造的子数组的最后一个元素必须为 true.在所有其他情况下，它可能为 true 或 false。
• 索引i指的是第一个false所在的正在构造的子数组的索引。例如，如果 arr_size #=> 4、nbr_false #=> 2 和 full_arr #=> false，则索引 i第一个 false 的 可以是 0 或 1。它不能是 2，因为这需要最后两个元素为 false。