Цикл в строках истинной таблицы

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 Я хочу это

[00015] 1-1-1-0 Я хочу это

[00016] 1-1-1-1

Искать 4элементы легко сделать цикл, но вы представляете таблицу с миллионами элементов.Ниже приведен код для иллюстрации моей первой мысли:

$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

С миллионами строк вам определенно нужно переместить логику выбора на стороне базы данных, или вам придется делать безумные вычисления на стороне PHP, что приводит к потенциальным проблемам с производительностью и памятью.

Предполагается, что у вас есть 4 столбца голосования, в которых хранится 1 или 0:

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

А если вы храните логические значения, вы можете разыграть его как целое число: WHERE CAST(vote1 AS SIGNED INTEGER) + ...

Answer 2

Рекурсивное решение выглядит так:

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-цифры и добавьте единицу. Таким образом, [0,1,1,1] становится (0111) b = (7) d + 1 = (8) d = 8.