计数二进制红宝石

Question

我有两个数组

[a0 b0 c0] 

[a1 b1 c1] 

我想计算两者之间所有可能的总和。可能的总和由每个列时隙仅包含1个元素组成。例如，一个可能的总和是

a0 + b1 + c1 

或

a1 + b1 + c1 

但不a1 + a0 + b0 + c0

换言之在实施例的总和将具有3个时隙，每一个仅具有1中的两个的元件阵列。从我的角度来看，这看起来像是以二进制计数，其中每个插槽只能取两个数字中的一个（0或1）。因此，在这个例子中

000表示所有的总和来自第一阵列

sum(000) = a0 + b0 + c0. 
sum(111) = a1 + b1 + c1 
sum(010) = a0 + b1 + c0 

你得到的备忘录的内容。

我想知道如何在ruby中做到这一点。我正在考虑一个复杂的解决方案，我计算一个二进制字符串，并为每个计数从数组中选择正确的元素。由于我想要所有可能的组合（2^n），我可以在单行中编码还是接近它？

Answer 1

▶ a1 = [11,12,13] 
#⇒ [11, 12, 13] 
▶ b1 = [21,22,23] 
#⇒ [21, 22, 23] 
▶ a1.zip(b1).reduce(&:product).map(&:flatten) 
#⇒ [[11, 12, 13], [11, 12, 23], [11, 22, 13], [11, 22, 23], 
#⇒ [21, 12, 13], [21, 12, 23], [21, 22, 13], [21, 22, 23]] 
▶ a1.zip(b1).reduce(&:product).map(&:flatten).map { |e| e.reduce &:+ } 
#⇒ [36, 46, 46, 56, 46, 56, 56, 66] 

UPD只是出于好奇这是写在红宝石@ pangpang的解决方案：

[0,1].repeated_permutation([a1.length, a2.length].min).map do |bits| 
    bits.each_with_index.reduce(0) do |memo, (e, i)| 
    memo + (e.zero? ? a1[i] : a2[i]) 
    end 
end 

Answer 2

这是一个蛮力的方法。我相信，有一种方法更优雅的方式与拉姆达要做到这一点，但我的大脑并没有在这个时候一天的工作方式：

2.1.2 :003 > a=[1,2,3] 
=> [1, 2, 3] 
2.1.2 :005 > b=[4,5,6] 
=> [4, 5, 6] 
2.1.2 :006 > 1.downto(0) do |outer| 
2.1.2 :007 >  1.downto(0) do |middle| 
2.1.2 :008 >  1.downto(0) do |inner| 
2.1.2 :009 >   puts (outer==1 ? b[0] : a[0]) + (middle==1 ? b[1] : a[1]) + (inner==1 ? b[2] : a[2]) 
2.1.2 :010?>  end 
2.1.2 :011?>  end 
2.1.2 :012?> end 
15 
12 
12 
9 
12 
9 
9 
6 

Answer 3

arr1 = [0,0,0] 
arr2 = [1,1,1] 

(0..(2**arr1.length-1)).each do |i| 
    sum = 0 
    bina = "%0#{arr1.length}b" % i # convert int to binary 
    bina.split("").each_with_index do |e,i| 
     e.to_i == 0 ? sum += arr1[i] : sum += arr2[i] 
    end 
    puts "#{bina} and #{sum}" 
end 

输出：

000 sum 0 
001 sum 1 
010 sum 1 
011 sum 2 
100 sum 1 
101 sum 2 
110 sum 2 
111 sum 3 

Answer 4

这是另一种实现@ pangpang答案的方法。我也试图解释这种方法的基本思想。

代码

def perm_sums(arr0, arr1) 
    sz = arr0.size 
    at = [arr0, arr1].transpose 
    (0...2**sz).map { |n| sz.times.reduce(0) { |t,i| t + at[i][n[i]] } } 
end 

例

arr0 = [1,2,3] 
arr1 = [6,7,8] 

perm_sums(arr0, arr1) #=> [6, 11, 11, 16, 11, 16, 16, 21] 

说明

对于上面的示例：

sz = arr0.size #=> 3 

at = [arr0, arr1].transpose #=> [[1, 6], [2, 7], [3, 8]] 

这当然与arr0.zip(arr1)相同。

e0 = (0...2**sz).map #=> #<Enumerator: 0...8:map> 

我们可以通过将其转换为一个数组查看此枚举的元素：

e0.to_a #=> [0, 1, 2, 3, 4, 5, 6, 7] 

的e0第一元件被传递到块和分配给该块变量：

n = e0.next #=> 0 

n=0没有那么有趣，因为它的二进制表示都是零位。让我们来看看，而不是在n=3：

n = e0.next #=> 1 
n = e0.next #=> 2 
n = e0.next #=> 3 

e1 = sz.times #=> #<Enumerator: 3:times> 
e1.to_a   #=> [0, 1, 2] 

块计算使用Fixnum#[]。的n=3二进制表示由字符串显示：

3.to_s(2).rjust(sz,'0') #=> "011" 

3[i]给出的第i个二进制值的最显著位：

3[0] #=> 1 
3[1] #=> 1 
3[2] #=> 0 

块计算如下进行。 reduce设置块变量t到的0初始值，然后将每个e1到该块中的三个要素：

t = 0 
i = e1.next  #=> 0 
t + at[i][n[i]] #=> 0 + at[0][n[0]] => [1, 6][3[0]] => [1, 6][1] => 6 

t = 6 
i = e1.next  #=> 1 
t + at[i][n[i]] #=> 1 + at[1][3[1]] => 1 + [2,7][1] => 8 

t = 8 
i = e1.next  #=> 2 
t + at[i][n[i]] #=> 8 + at[2][n[2]] => 8 + [3,8][3[2]] => 8 + [3,8][0] => 11 

i = e1.next 
    #=> StopIteration: iteration reached an end 

所以数量3被映射到11。其他计算也是相似的。

请注意，如果我们将at[i][n[i]]替换为at[i][n[sz-1-i]]（即将位从高位提取到低位），我们将得到相同的答案。