Бесконечный перебор несколькольких целых значений

Question

Предположим, я хочу бесконечно перебирать несколько целых значений, пока не найдется их подходящая комбинация. Если значение одно, то это делается легко: мы просто перебираем циклом while это значение. Что делать, если этих значений несколько? P.S. думаю, это можно сделать с помощью BFS, но нет ли более простого способа?

UPD: Например, у меня есть целочисленная переменная a и функция check(int a), возвращающая true если это значение подходит. Перибирать все значения в данном случае можно так:

int a = 0;
while(!check(a) && !check(-a)) {
    ++a;
}

Что делать, если у меня есть целочисленные переременные a, b и функция check(int a, int b)? Как перебирать?

Answer 1

Псевдокод:

M = 0

Повторять:
    для a от 0 до M:
        b = M
        Проверить (a, b)
    для b от 0 до (M-1)
        a = M
        Проверить (a, b)
    M = M + 1

То есть это похоже на то, что вы пишете:

Т.е. (для двух значений) мы предполагаем, что находимся на клетчатом поле в клетке (0, 0) потом рассматриваем соседние для этой клетки клетки, потом соседние для соседей и т.д. Но этот способ мне не очень нравится. Ему нужно достаточно много дополнительной памяти, да и код некрасивым будет.

Только в моём варианте не надо хранить список клеток и искать их соседей, потому что каждая итерация соседей будет представлять из себя полоски клеток сверху и справа от квадрата, который на каждой итерации увеличивается на 1.

Для более двух переменных тот же принцип, но код немного посложнее.

UPD: Понял, что можно сделать ещё проще:

S = 0
Повторять:
    для a от 0 до S:
        b = S - a
        Проверить (a, b)
    S = S + 1

Answer 2

Когда вы перебирали значения одной переменной, то вы просто двигались по оси OX от нуля в сторону положительных значений до бесконечности. И с этим проблем нет, бери да перебирай.

Теперь вам надо перебирать два числа. Т.е. как-то одновременно двигаться по двумя осям координат "закрашивая" всю проверенную область. Как вы будете её закрашивать - ваше дело, но если нужен простой перебор всех вариантов в "лоб", то двигаться только вдоль одной оси - не выйдет: она же бесконечная. Поэтому можно попробовать двигаться по диагонали заливая всё от угла 0,0 в сторону угла +бесконечность_по_X,+бесконечность_по_Y.

Путь, который пройдёт ваш алгоритм можно представить как на картинке ниже:

А сам код (мой пример на php) может быть, например, таким (в переменной dir - направление движения - или в сторону оси a или в сторону оси b, а остальное понятно и так):

const DIR_A = 0;
const DIR_B = 1;

$a = 0;
$b = 0;
$dir = DIR_A;

$dots = [];
while (count($dots) < 16) {
    $dots[] = [$a, $b];
    if ($dir === DIR_A) {
        if ($b > 0) {
            $b--;
            $a++;
        } else {
            $a++;
            $dir = DIR_B;
        }
    } else {
        if ($a > 0) {
            $a--;
            $b++;
        } else {
            $b++;
            $dir = DIR_A;
        }
    }
}

foreach ($dots as $dot) {
    echo "[{$dot[0]}, {$dot[1]}], ";
}
echo "...\n";

В итоге получается вот такой вывод:

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

Answer 3

Ну, если ты хочешь перебирать несколько значений в поисках подходящей их комбинаций, то ... эээ ... может цикл в цикле сделать ?!

bool isFound = false;

for (int a = start; a < end; a++) {
  for (int b = start; b < end; b++) {
    ...
      if (check(a, b, ..., n)) {
        // Сохрани найденные значения
        isFound = true;
        break;
      }
    ...
    if (isFound) break;
  }
  if (isFound) break;
}

Только не перебирай до бесконечности! Это как-то долго что ли...