ruby - 位数组 - 所有可能的组合

Question

我有 0 和 1 的数组。我需要一个返回“下一个”数组的函数。像这样的东西：

f([0,0,0,0]) -> [0,0,0,1]
f([0,0,0,1]) -> [0,0,1,0]
f([0,1,1,1]) -> [1,0,0,0]

是否有任何库函数或者我需要自己编码？

Answer 1

Ruby 包含一种在二进制和 base 10 之间转换的简单方法。

"0010".to_i(2)
=> 2

13.to_s(2)
=> "1101"

所以做你需要的一个简单的方法是

def f(a)
  (a.join.to_i(2) + 1).to_s(2).split("").map{ |v| v.to_i }
end

这是添加两个 nbit 数字的方法。

def nbit_addition(a, b)
  bit1 = toBits(a)
  bit2 = toBits(b)
  bitLength = bit1.length > bit2.length ? bit1.length : bit2.length
  bit3 = []
  for i in 0...bitLength
    bit1[i] = 0 if bit1[i].nil? 
    bit2[i] = 0 if bit2[i].nil? 
    bit3[i] = 0 if bit3[i].nil?
    bit3[i] += (bit1[i] + bit2[i])
    if bit3[i] > 1 
      bit3[i + 1] = 0 if bit3[i + 1].nil?
      bit3[i] %= 2
      bit3[i + 1] += 1
    end 
  end 
  bit3.join.to_s.reverse.to_i(2)
end 

def toBits(value)
  bit = []
  value.to_s(2).reverse.split(//).each { |b| bit << b.to_i } 
  return bit 
end 

Answer 2

如果您想生成所有可能的组合（如标题所示），那么它们实际上是排列（重复）。

f = [0,1].repeated_permutation(4)
16.times {p f.next}

输出：

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 1, 0, 0]
[0, 1, 0, 1]
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 0, 0, 0]
[1, 0, 0, 1]
[1, 0, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 0, 1]
[1, 1, 1, 0]
[1, 1, 1, 1]

Answer 3

将位数组转换为数字非常简单：

[0,1,1,1].inject(0) { |number,bit| number * 2 + bit }
 => 7

当然很容易得到下一个数字：

7.succ
 => 8

...并且很容易将其转换回位数组：

8.to_s(2).chars.map(&:to_i)
 => [1, 0, 0, 0] 

也就是说，如果你必须这样做，你可能应该重新考虑为什么你首先有一个位数组。8是比 更合理的数字表示[1, 0, 0, 0]。

Answer 4

class Array
  def binary_succ(lindex=nil)
    lindex ||= size - 1    
    if lindex >= 0
      if self[lindex] == 0 then self[lindex] = 1
      else self[lindex] = 0; binary_succ(lindex-1) end
    end
    self
  end
end

[0,1,1,1].binary_succ #=> [1,0,0,0]

Answer 5

我很无聊，所以这是一个不涉及对数组进行字符串化的解决方案

def succ arr
  overflow = false
  rev = arr.reverse
  rev[0] += 1
  rev.map do |el|
    el += 1 if overflow
    case el
    when 0, 1
      overflow = false
      el
    when 2
      overflow = true
      0
    end
  end.reverse
end

succ [0,0,0,0] # => [0, 0, 0, 1]
succ [0,0,0,1] # => [0, 0, 1, 0]
succ [0,1,1,1] # => [1, 0, 0, 0]