algorithm - 满足给定约束的模式组合

Question

给出了由 1 和 0 组成的模式。总是7位，3位为1，4位为0

示例 - 1100010

约束是一次考虑 2 个 0 并将它们替换为 1。我需要找到所有这些可能的组合。

到目前为止我的想法是，找到 0 的索引并运行 for 循环以在每次运行时选择 2 个索引并获得输出。

例子-

给定模式 - 1100010

所需输出 -1111010、1110110、1110011、1101110、1101011、1100111

我可以详尽地做到这一点。以更优化的方式执行此操作的任何建议都将非常有帮助。

Answer 1

您的问题归结为找到 4 选择 2 的所有组合。您获取零索引的想法是一个很好的起点。

对于给定的示例，1100010，我们有以下内容:

1 1 0 0 0 1 0
| | | | | | |
V V V V V V V 
0 1 2 3 4 5 6   // indices here assuming base 0

因此我们的零索引向量是 {2, 3, 4, 6}。

现在，我们可以生成零索引向量的所有组合选择 2(SO 或网络上有几种很棒的算法很容易获得)并进行适当的替换以生成我们的输出。

伪代码:

inputVec = {1,1,0,0,0,1,0}
zeroIndex = {}

for i in 0 to (length(inputVec) - 1)
    if (inputVec[i] == 0)
        zeroIndex.push_back(i)     // zeroIndex = {2, 3, 4, 6} for the given example

// initialize output vector to the input vector
newOutput = inputVec
myCombos = generateCombos(zeroIndex, 2) // matrix of combinations with 2 columns

for i in 0 to (length(myCombos) - 1) {
    newOutput[myCombos[i, 0]] = 1
    newOutput[myCombos[i, 1]] = 1
    print(newOutput)

    // reset output vector
    newOutput = inputVec
}

在上面的算法中，generateCombos 将输出以下内容:

     [,0] [,1]
[0,]    2    3
[1,]    2    4
[2,]    2    6
[3,]    3    4
[4,]    3    6
[5,]    4    6

概述的算法扩展到输入向量具有任意长度且具有任意数量的 0 和 1 的一般情况。