рекурсия вместо многократных циклов

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

private static void allCombinations(List<String>... lists) {
    if (lists.length == 3) {
        for (String s3 : lists[0]) {
            for (String s1 : lists[1]) {
                for (String s2 : lists[2]) {
                    System.out.println(s1 + "-" + s2 + "-" + s3);
                }
            }
        }
    }
    if (lists.length == 2) {
        for (String s3 : lists[0]) {
            for (String s1 : lists[1]) {
                    System.out.println(s1 + "-" + s3);
            }
        }
    }
}

java loops recursion combinatorics
person Community    schedule 16.10.2008    source источник

Ответы (4)


arrow_upward
3
arrow_downward

Вот простая рекурсивная реализация:

private static void allCombinations(List<String>... lists) {
  allCombinations(lists, 0, "");
}

private static void allCombinations(List<String>[] lists, int index, String pre) {
  for (String s : lists[index]) {
    if (index < lists.length - 1) {
      allCombinations(lists, index + 1, pre + s + "-");
    }else{
      System.out.println(pre + s);
    }
  }
}
person Rasmus Faber    schedule 16.10.2008
comment
это не дает того результата, который дал исходный код. обратите внимание на порядок петель s3,s1,s2. - person Amir Arad; 16.10.2008
comment
А, я предположил, что это ошибка. Во всяком случае, это должен быть общий принцип рекурсивного решения. Вы можете выполнить некоторое преобразование переменной-индекса, прежде чем использовать ее в строке с оператором for, чтобы получить другой порядок циклов. - person Rasmus Faber; 16.10.2008

arrow_upward
1
arrow_downward

Вам особенно нужно, чтобы он был рекурсивным? Я бы сделал это нерекурсивным, но все же не особым случаем:

public static void allCombinations(List<String>... lists) {
    int[] indexes = new int[lists.length];

    while (incrementIndexes(lists, indexes)) {
        StringBuilder builder = new StringBuilder();
        for (int i=0; i < indexes.length; i++) {
            if (i != 0) {
                builder.append("-");
            }
            builder.append(lists[i].get(indexes[i]));
        }
        System.out.println(builder);
    }
}

private static boolean incrementIndexes(List<String>[] lists, int[] indexes) {
    for (int depth = indexes.length-1; depth >= 0; depth--) {
        indexes[depth]++;
        if (indexes[depth] != lists[depth].size()) {
            return true;
        }
        // Overflowed this index. Reset to 0 and backtrack
        indexes[depth] = 0;
    }
    // Everything is back to 0. Finished!
    return false;
}
person Jon Skeet    schedule 16.10.2008
comment
В какой-то степени вы эмулируете то, что рекурсивное решение все равно делало бы (управляя списком индексов). Однако я ожидаю, что ваше решение более эффективно, но, возможно, немного менее читабельно, чем рекурсивный эквивалент. - person Richard Dorman; 16.10.2008
comment
Это, безусловно, эффективно эмулирует рекурсивную версию. В данном конкретном случае решение, предложенное Расмусом, проще, потому что текущее состояние легко записать в виде строки, а затем добавить к ней. В более общем случае необходимости каждого из текущих элементов я подозреваю (продолжение) - person Jon Skeet; 16.10.2008
comment
вам все равно придется хранить набор индексов (или строк) - не имеет большого значения, рекурсивный он или нет в этот момент. Я попытаюсь придумать альтернативную рекурсивную форму :) - person Jon Skeet; 16.10.2008
comment
Как правило, рекурсивные решения несут больше накладных расходов, чем их нерекурсивные аналоги (в основном из-за распределения стека), но часто их легче читать (отличным примером является решение Расмуса). - person Richard Dorman; 16.10.2008

arrow_upward
1
arrow_downward

Вот обобщенная рекурсивная версия. Он жалуется на непроверенное создание универсального массива в тестовом коде, но сам код перестановки в порядке:

import java.util.*;

public class Test
{
    public interface Action<T> {
        void execute(Iterable<T> values);
    }

    public static void main(String[] args) {
        List<String> first = Arrays.asList(new String[]{"1", "2", "3"});
        List<String> second = Arrays.asList(new String[]{"a", "b", "c"});
        List<String> third = Arrays.asList(new String[]{"x", "y"});
        Action<String> action = new Action<String>() {
            @Override public void execute(Iterable<String> values) {
                 StringBuilder builder = new StringBuilder();
                 for (String value : values) {
                     if (builder.length() != 0) {
                         builder.append("-");
                     }
                     builder.append(value);
                 }
                 System.out.println(builder);
            }
        };
        permute(action, first, second, third);
    }

    public static <T> void permute(Action<T> action, Iterable<T>... lists) {
        Stack<T> current = new Stack<T>();
        permute(action, lists, 0, current);
    }

    public static <T> void permute(Action<T> action, Iterable<T>[] lists,
        int index, Stack<T> current) {
        for (T element : lists[index]) {
            current.push(element);
            if (index == lists.length-1) {
              action.execute(current);
            } else {
              permute(action, lists, index+1, current);
            }
            current.pop();
        }
    }
}
person Jon Skeet    schedule 16.10.2008

arrow_upward
0
arrow_downward

вот мое рекурсивное решение с правильным порядком, основанное на решении Расмуса. это работает, только если все списки имеют одинаковый размер.

import java.util.Arrays;
import java.util.List;


public class Test {

        public static void main(String[] args) {
        List<String> first = Arrays.asList(new String[]{"1", "2", "3"});
        List<String> second = Arrays.asList(new String[]{"a", "b", "c"});
        List<String> third = Arrays.asList(new String[]{"x", "y", "z"});
        allCombinations (first, second, third);
        }

        private static void allCombinations(List<String>... lists) {
              allCombinations(lists, 1, "");
        }

        private static void allCombinations(List<String>[] lists, int index, String pre) {
            int nextHop = hop(index, lists.length-1);
          for (String s : lists[index]) {
            if (index != 0) {
              allCombinations(lists, nextHop, pre + s + "-");
            } else System.out.println(pre + s);
          }
        }
        private static int hop(int prevIndex, int maxResult){
            if (prevIndex%2 == 0){
                return prevIndex-2;
            } else {
                if (prevIndex == maxResult) 
                    return prevIndex-1;
                int nextHop = prevIndex+2;
                if (nextHop > maxResult){
                    return maxResult;
                } else return nextHop;
            }
        }

}

решение «правильного упорядочения», которое позволяет списки разных размеров, должно начинаться с последнего списка и работать в обратном направлении к первому списку (списки [0]), добавляя элемент либо в начало, либо в конец строки «pre». и прохождение его дальше. снова первый список напечатает результат. Я бы закодировал это, но обед готов, а девушке начинает не нравиться stackoverflow...

person Amir Arad    schedule 16.10.2008