循环在真相表行

Question

关于真实表格中的循环，我有一个问题。我需要获得所有行，其中只有3个位置的值等于1，看样本：

对于有4个元素的表存在16种可能性，但我只需要4个。所以我需要获得4个位置而不通过所有其他位置：

[00002] 0-0-0-1

[00003] 0-0-1-0

[00004] 0-0-1-1

[00005] 0-1-0-0

[00006] 0-1-0-1

[00007] 0-1-1-0

[00008] 0-1-1-1我想要这个

[00009] 1-0-0-0

[00010] 1-0-0-1

[00011] 1-0-1-0

[00012] 1-0-1-1我想要这个

[00013] 1-1-0-0

[00014] 1-1-0-1我想要这个

[1-115] 1-1-1-0我想要这个

[00016] 1-1-1-1

寻找4个元素很容易做一个循环，但你想象一个有数百万个元素的表。以下是我首先想到的ilustre代码：

$t1 = time();

echo "\n\n";
echo "################ Started in :" . date('d/m/Y H:i:s', $t1);
echo "\n\n";

$votesCount = 4;
$possibilities = pow(2, $votesCount);

for ($i = 0; $i < $possibilities; $i++) {
  $binare = str_pad(decbin($i), $votesCount, 0, STR_PAD_LEFT);
  $arrayBinare = str_split($binare);
  $posVote = str_pad($i + 1, 5, 0, STR_PAD_LEFT);
  $c = "[" . $posVote . ']  ' . implode('-', $arrayBinare);
  if (array_sum($arrayBinare) == 3) {
    echo "<b>$c</b> I want this<br>";
    continue;
  }
  echo "$c <br>";
}

$t2 = time();
echo "\n";
echo "################ Finished in:" . date('d/m/Y H:i:s', $t2);
echo "\n";
echo "################ Duraction: " . ($t2 - $t1) . ' seconds';
echo "\n";

Answer 1

递归解决方案如下所示：

function Enumerate(len, rem)
    if rem = 0 then return [0]^len
    if len < rem then return {}
    if len = rem then return {[1]^rem}
    return ({[0]} & Enumerate(len - 1, rem))
            union
           ({[1]} & Enumerate(len - 1, rem - 1))

符号[1]^rem表示仅包含rem的长度为1的向量;运算符&返回通过将来自RHS的向量连接到LHS中的向量而获得的所有向量。当它检测到无法获得解决方案或只有一种可能的解决方案时，这会短路，但您可以将其删除以打印所有排列并检查它们。执行示例：

Enumerate(4, 3) = {[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]}
    4 < 3? no
    4 = 3? no
    [0] & Enumerate(3, 3) = [0] & [1,1,1] = [0,1,1,1]
        3 = 0? no
        3 < 3? no
        3 = 3? yes, return [1,1,1]
    [1] & Enumerate(3, 2) = [1] & ([0,1,1],[1,0,1],[1,1,0]| = {[1,0,1,1],[1,1,0,1],[1,1,1,0]}
        2 = 0? no
        3 < 2? no
        3 = 3? no
        [0] & Enumerate(2, 2) = [0] & [1,1] = [0,1,1]
            2 = 0? no
            2 < 2? no
            2 = 2? yes, return [1,1]
        [1] & Enumerate(2, 1) = [1] & {[0,1],[1,0]) = {[1,0,1],[1,1,0]}
            1 = 0? no
            2 < 1? no
            2 = 1? no
            [0] & Enumerate(1, 1) = [0] & [1] = [0,1]
                1 = 0? no
                1 < 1? no
                1 = 1? yes, return [1]
            [1] & Enumerate(1, 0) = [1] & [0] = [1,0]
                0 = 0? yes, return [0]

如果您希望这是迭代而不是递归，那么添加堆栈数据结构并在while循环中显式管理堆栈，而堆栈不为空。

如果您希望每个解决方案在所有解决方案的有序空间中的位置 - 只需将向量解释为len-digit二进制数字的数字序列并添加一个。因此，[0,1,1,1]变为（0111）b =（7）d + 1 =（8）d = 8。

Answer 2

拥有数百万行，您肯定希望在数据库端移动选择逻辑，否则您将不得不在PHP端进行大量的计算，从而导致潜在的性能和内存问题。

假设您有4个投票列存储1或0：

SELECT *
FROM votes
WHERE (vote1 + vote2 + vote3 + vote4) = 3

如果你正在存储布尔值，你可以把它作为一个整数：WHERE CAST(vote1 AS SIGNED INTEGER) + ...