Ruby - 在另一个长度未知的数组中均匀分布和交错/交织一个数组的元素

Question

我有两个长度未知的数组。一个的元素需要均匀(尽可能均匀地)分布在另一个中。

示例假设数组中的 + 元素是实际值的占位符。我省略了数组逗号分隔符以消除视觉噪音并使模式更加明显。

a = [++++++++++] # 10 element array with + characters representing array items

b = [] # empty array
a.interweave(b) #=> [++++++++++]

b = [1]
a.interweave(b) #=> [+++++1+++++]

b = (1..2).to_a
a.interweave(b) #=> [+++1+++2++++]

b = (1..3).to_a
a.interweave(b) #=> [++1++2+++3+++]  # any remaining + are distributed to the end chunks.

b = (1..4).to_a
a.interweave(b) #=> [++1++2++3++4++]

b = (1..5).to_a
a.interweave(b) #=> [+1+2++3++4++5++]

b = (1..6).to_a
a.interweave(b) #=> [+1+2+3+4++5++6++]

b = (1..7).to_a
a.interweave(b) #=> [+1+2+3+4+5+6++7++]

b = (1..8).to_a
a.interweave(b) #=> [+1+2+3+4+5+6+7+8++]

b = (1..9).to_a
a.interweave(b) #=> [+1+2+3+4+5+6+7+8+9+]

b = (1..10).to_a
a.interweave(b) #=> [+1+2+3+4+5+6+7+8+9+10]

b = (1..11).to_a
a.interweave(b) #=> [+,1,+,2,+,3,+,4,+,5,+,6,+,7,+,8,+,9,+,10,11] # the remaining elements from b are added to the end

我正在寻找 Ruby 中的高性能算法。

Answer 1

另一种方式:

def weave(xx,yy)
  x = xx.dup
  y = yy.dup
  n_extra = [y.size - x.size + 1, 0].max
  y_extra = y.slice!(y.size - n_extra, n_extra)
  z = x.class.new
  loop do
    z += (x.slice!(0,((x.size)/(y.size+1.0)).floor) + y.slice!(0,1))
    break if y.empty?
  end
  z + x + y_extra
end         

x = ('-'*10).chars
  # => ["-", "-", "-", "-", "-", "-", "-", "-", "-", "-"]

p weave(x, ['a', 'b', 'c'])
  # => ["-", "-", "a", "-", "-", "b", "-", "-", "-", "c", "-", "-", "-"]

p weave(x, ['a', 'b', 'c']).join # => "--a--b---c---"
p weave('----------', 'abc')     # => "--a--b---c---"

y = (1..12).each_with_object([]) {|i,a| a << ('a'..'z').to_a.first(i)}

y.each {|e| p weave(x, e).join}
"-----a-----"
"---a---b----"
"--a--b---c---"
"--a--b--c--d--"
"-a-b--c--d--e--"
"-a-b-c-d--e--f--"
"-a-b-c-d-e-f--g--"
"-a-b-c-d-e-f-g-h--"
"-a-b-c-d-e-f-g-h-i-"
"-a-b-c-d-e-f-g-h-i-j"
"-a-b-c-d-e-f-g-h-i-jk"
"-a-b-c-d-e-f-g-h-i-jkl"

编辑:我对原来的解决方案做了一些修改:

• 添加了 weave 的前两行，因此参数不会被更改。
• 简化了循环。
• 在@Kal 的建议下，从 (arr + x + y_extra) 的末尾删除了 .join。
• 将 z = [] 更改为 z = x.class.new 以允许 weave 的参数为数组或字符串。

关于 ((x.size)/(y.size+1.0)).floor 的一句话。假设 x = ['-','-','-','-','-','-'] 和 y = ['a', 'b', 'c']。然后:

• 循环的第一次迭代后，z => ['-', 'a'], x => ['-','-','-', '-','-'] 和 y => ['b', 'c']。
• x 的剩余部分将被划分为 y.size+1.0 => 3.0 间隔，每个间隔有 x.size/3.0 => 5/3.0 => 1.67 个元素，如果 x 的元素可以被分割。因为它们不能被分割，并且较大的组在右边，我们从 x 中剥离 1.67.floor => 1 元素，附加它和y 到 z 的下一个元素，然后重复，直到 y.empty？ => 真。