Java-рекурсия по 2 параметрам и в двух направлениях

Я хочу обобщить два параметра одновременно в общем виде. Вот некоторые объяснения:

Вот так должны выглядеть вызовы функций Func(int a, int b):

  • Звоните 0: Func(0, 0)
  • Звоните 1: Func(0, 1)
  • Звоните 1: Func(1, 0)
  • Звоните 1: Func(0, -1)
  • Звоните 1: Func(-1, 0)

Как бы я реализовал это в коде, обеспечив следующие утверждения:

  • Все возможные комбинации a INRANGE (-INF, INF) а также b INRANGE (-INF, INF) считаются.
  • Нет никаких накладных расходов, я имею в виду, что одна и та же функция не используется несколько раз в рекурсии.

Позже я хочу расширить его, чтобы сделать то же самое по 7 параметрам.

С уважением.

Источник

4 ответа

Решение

Вот мой взгляд на спиральный подход:

// this is your function
static void func(int x, int y)
{
  System.out.println("x = "+x+", y = "+y);
}

// this calls func for all possible combinations of signs of the variables in arr
static void allPossibleSigns(int pos, Integer... arr)
{
  if (pos == arr.length)
  {
     func(arr[0], arr[1]); // not really generic
  }
  else
  {
     allPossibleSigns(pos+1, arr);
     arr[pos] = -arr[pos];
     if (arr[pos] != 0)
        allPossibleSigns(pos+1, arr);
  }
}

static void caller()
{
  for (int t = 0; t < MAX; t++)
  for (int x = 0; x <= t; x++)
  {
     int y = (t-x);
     allPossibleSigns(0, x, y);
  }
}

Если вы хотите что-то более общее, чем func(arr[0], arr[1]);Вы можете заменить его на:

Method[] methods = NewMain.class.getMethods();
for (Method m: methods)
{
   if (m.getName().equals("func"))
      m.invoke(null, arr);
}

и добавить проверку ошибок. я использовал Integer... вместо int... в printAllPossibleSigns из-за этого подхода (выше не работает для int...). Это предполагает, что у вас есть только одна функция с именем func, Если это не так, вам придется добавить некоторые дополнительные проверки.

За MAX = 4, он печатает:

x = 0, y = 0
x = 0, y = 1
x = 0, y = -1
x = 1, y = 0
x = -1, y = 0
x = 0, y = 2
x = 0, y = -2
x = 1, y = 1
x = 1, y = -1
x = -1, y = -1
x = -1, y = 1
x = 2, y = 0
x = -2, y = 0
x = 0, y = 3
x = 0, y = -3
x = 1, y = 2
x = 1, y = -2
x = -1, y = -2
x = -1, y = 2
x = 2, y = 1
x = 2, y = -1
x = -2, y = -1
x = -2, y = 1
x = 3, y = 0
x = -3, y = 0

Как это будет расширено до 3-х переменных, может быть не совсем понятно, поэтому вот caller для 3 переменных:

static void caller()
{
  for (int t = 0; t < MAX; t++)
  for (int x = 0; x <= t; x++)
  for (int y = 0; y <= (t-x); y++)
  {
     int z = (t-x-y);
     printAllPossibleSigns(0, x, y, z);
  }
}

И это все, что вы должны изменить, наряду с вашей функцией, очевидно, и func(arr[0], arr[1]); если вы не выбрали общий подход.

Источник

Я предлагаю спираль, не рекурсивно простую. Для удобства чтения ход выбирается снова на каждом шаге.

int x = 0;
int y = 0;
for (int t = 0; t < 100; ++t) {
    func(x, y);
    if (x <= 0 && y == 0) { // Widen spiral.
        --x;
        ++y; // So next condition takes next.
    } else if (x < 0 && y >= 0) { // Left, upper quadrant.
        ++x;
        ++y;
    } else if (x >= 0 && y > 0) { // Right, upper.
        ++x;
        --y;
    } else if (x >= 0 && y <= 0) { // Right, lower.
        --x;
        --y;
    } else if (x < 0 && y < 0) { // Left, lower.
        --x;
        ++y;
    } else {
        throw new IllegalStateException("x = " + x + ", y = " + y);
    }
}

Я не пробовал код! Проверьте условия.

Источник

Может быть, некоторые знания комбинаторики помогут здесь. Для меня это выглядит так, будто у вас есть набор элементов от -N до +N. Теперь вы хотите вызвать функцию для каждого изменения длины == 7 этих элементов.

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

Я бы написал Iterator который доставляет новую вариацию элементов (которые являются параметрами вашей функции) при каждом вызове next().

Реализация такого итератора могла бы BigInteger, если вам нужны большие цифры. Вы могли бы использовать Array или же List и изменить его элементы на каждой итерации. Если вы ищете комбинаторные алгоритмы или алгоритмы перестановки / вариации, вы можете найти детали и, возможно, даже реализации.

Другой (похожий) способ (с большими накладными расходами, я думаю) будет использовать только одно число (например, BigInteger), чтобы отметить текущее изменение. На каждой итерации вы добавляете 1 к этому номеру индекса вариации.

Чтобы получить параметры из этого числа, вы должны выполнить базовое преобразование для этого индекса вариации. Основой будет количество элементов в вашем наборе элементов. Полученные цифры числа имеют диапазон от 0 до количества элементов -1. Отсюда вы можете использовать каждую цифру, чтобы получить параметры для вызова вашей функции из списка элементов.

Я сделал, чем некоторое время назад, и это прекрасно работает. Не могу обещать, чем я могу найти это.

Источник

Для n размеров:

Ниже я использую положительные числа для координат. Для каждой положительной (больше 0) координаты в решении, делающем координату отрицательной, также есть решение (почти в 2 раза больше решений). (Использование положительных чисел упрощает чтение решения.)

Это решение для координатного вектора размерности n. Координаты выбираются с постоянно растущим "радиусом" = суммой координат.

static void func(int[] x) {
    System.out.printf("%s%n", Arrays.toString(x));
}

/**
 * Call many funcs with several coordinates.
 * @param x n-dimensional coordinates.
 * @param fromI starting index for variable coordinates.
 * @param r radius, equal to the sum of x[>= fromIndex].
 * @param t downward counter limiting the number of calls.
 * @return new value of t.
 */
static int callFuncsForRadius(int[] x, int fromIndex, int r, int t) {
    if (t <= 0) {
        return t;
    }
    if (fromIndex >= x.length) { // Nothing more to vary.
        if (r == 0) { // Read radius sum.
            func(x);
            --t;
        }
        return t;
    }
    for (int rNext = r; rNext >= 0; --rNext) {
        x[fromIndex] = rNext;
        t = callFuncsForRadius(x, fromIndex + 1, r - rNext, t);
        if (t <= 0) {
            break;
        }
    }
    return t;
}

static int callFuncs(int[] x, int t) {
    int r = 0;
    while (t > 0) {
        t = callFuncsForRadius(x, 0, r, t);
        ++r;
    }
    return t;
}

public static void main(String[] args) {
    int n = 3;
    int[] x = new int[n];
    int t = 10; // N^n, where N = 2^31.
    callFuncs(x, t);
}
Источник
Другие вопросы по тегам