11

我已经连续绞尽脑汁3个小时了，但我仍然不明白，所以我在这里问。（我在标题中写了 Python，但这可能适用于几乎任何语言）

假设我有一个固定长度 n 的位数组（但它也可能是定义范围内的整数），比如说 5。

array=[0,1,1,0,0]

现在，我如何生成所有数组，这些数组在数字范围内是可能的（在位的情况下，2）。

所以：

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

我曾尝试在这里寻找解决方案，但我总能找到类似的东西，但并不能完全解决我的问题。

为了解决这个问题，我尝试了各种循环，但我总是会多次获得一种可能性（不应该发生），或者没有获得所有可能的可能性。

我可以使用 if 语句来做到这一点（检查组合是否已经存在），但这似乎非常简单。

有没有一种简单的方法，只使用循环来获得所有的可能性？

谢谢

编辑：因为这在下面提到，不，这不是家庭作业。这是为了研究以实现二元状态的贝叶斯网络。（开关）。

4

5 回答 5

16

在 Python 中，使用itertools来处理这样的事情

from itertools import product
for i in product([0,1], repeat=5): 
    print i

产量：

(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
etc...
于 2012-10-20T19:05:33.747 回答
5

我将通过从 0 循环到 31 (0b11111) 并将二进制表示转换为固定长度的数组来解决这个问题。

你没有用语言标记它，所以我不确定如何给你示例代码，但这种方法应该有效。

1: 00001
2: 00010
3: 00011
...
30:11110
31:11111

编辑：刚刚看到你用 Python 标记了这个问题。实现上述算法的示例 python 代码：

listLength=5
for x in range(0,2**listlength):
    print(list(bin(x)[2:].zfill(listlength)))

打印出来：

['0', '0', '0', '0', '0']
['0', '0', '0', '0', '1']
['0', '0', '0', '1', '0']
['0', '0', '0', '1', '1']
['0', '0', '1', '0', '0']
['0', '0', '1', '0', '1']
['0', '0', '1', '1', '0']
['0', '0', '1', '1', '1']
['0', '1', '0', '0', '0']
['0', '1', '0', '0', '1']
['0', '1', '0', '1', '0']
['0', '1', '0', '1', '1']
['0', '1', '1', '0', '0']
['0', '1', '1', '0', '1']
['0', '1', '1', '1', '0']
['0', '1', '1', '1', '1']
['1', '0', '0', '0', '0']
['1', '0', '0', '0', '1']
['1', '0', '0', '1', '0']
['1', '0', '0', '1', '1']
['1', '0', '1', '0', '0']
['1', '0', '1', '0', '1']
['1', '0', '1', '1', '0']
['1', '0', '1', '1', '1']
['1', '1', '0', '0', '0']
['1', '1', '0', '0', '1']
['1', '1', '0', '1', '0']
['1', '1', '0', '1', '1']
['1', '1', '1', '0', '0']
['1', '1', '1', '0', '1']
['1', '1', '1', '1', '0']
于 2012-10-20T07:25:47.127 回答
2 
import numpy as np
def all_combinations(width, vals):
    return np.array(np.meshgrid(*[vals]*width,
                    indexing='ij')).reshape((width,-1)).transpose()

print(all_combinations(width=3, vals=[0,1]))
print(all_combinations(width=2, vals=['a','b','c']))

输出：

[[0 0 0]
 [0 0 1]
 [0 1 0]
 [0 1 1]
 [1 0 0]
 [1 0 1]
 [1 1 0]
 [1 1 1]]
[['a' 'a']
 ['a' 'b']
 ['a' 'c']
 ['b' 'a']
 ['b' 'b']
 ['b' 'c']
 ['c' 'a']
 ['c' 'b']
 ['c' 'c']]
于 2018-01-27T04:42:47.120 回答
1

这是一个通用的递归伪代码来做你想要的。

array_combination is function (length, elements)
  if length < 1 
  then abort
  end if

  declare arrays as new array
  if length is 1 
  then
    loop for element in elements
      declare element_array as new array
      set element_array[0] to element
      append element_array to arrays
    end loop
  else
    loop for array in array_combination(length - 1, elements)
      loop for element in elements
        declare element_array as new array
        set element_array[0] to element
        append array to element_array
        append element_array to arrays
      end loop
      append array to arrays
    end loop
  end if
  return arrays
end function

对于给定的示例，您可以将此函数称为“array_combination(5, [1,0])”。有更好的方法来构建它，但是a）我太老了，不能做作业，b）我不知道你的作业的限制，c）我不想让你作弊太明显。

请注意重复代码和消除常见子表达式的机会，以及极其浪费的内存分配和缓存滥用。但是，我假设这是第一季度的计算机科学作业，所以他们可能不会反对你。

于 2012-10-20T07:58:51.983 回答
0

一个古怪的解决方案是认为，在每次“迭代”直到大小为 n 时，您都会将新维度中 0 或 1 的组合数量加倍。

从最简单的情况 n=1 开始：

[[0],
 [1]]

当 n=2 时，在分别添加 0 和 1 之前重复数组：

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

您可以继续前进，直到尺寸为 n。实现这一点，您将拥有：

BIN = np.array([[0], [1]])
for i in range(n-1):
    size = BIN.shape[0]
    BIN = np.vstack((np.hstack((BIN, np.zeros((size, 1)))), np.hstack((BIN, np.ones((size, 1))))))

这不是最漂亮的解决方案，但它开启了使用递归实现的可能性。

于 2022-02-01T19:38:23.777 回答