Рекурсия вместо многократных циклов
Я хочу, чтобы этот метод работал для любого заданного количества аргументов, я могу сделать это с помощью генерации кода (с большим количеством уродливого кода), можно ли это сделать с помощью рекурсии? если да, то как? Я понимаю рекурсию, но не знаю, как это написать.
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);
}
}
}
}
Ответы 4
Вам особенно нужно, чтобы он был рекурсивным? Я бы сделал это нерекурсивным, но все же не особым случаем:
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;
}
Это определенно эффективно имитирует рекурсивную версию. В этом конкретном случае решение, данное Расмусом, проще, потому что легко захватить «текущее состояние» в виде строки, а затем добавить к ней. Я подозреваю, что в более общем случае вам понадобится каждый из текущих предметов (продолжение)
в любом случае вам придется сохранить набор индексов (или строк) - не имеет большого значения, рекурсивен он или нет. Попробую придумать альтернативную рекурсивную форму :)
Обычно рекурсивные решения влекут за собой больше накладных расходов, чем их нерекурсивные аналоги (в основном в виде распределения стека), но часто их легче читать (решение Расмуса является отличным примером).
Вот простая рекурсивная реализация:
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);
}
}
}
это не дает результата, который давал исходный код. обратите внимание на порядок циклов s3, s1, s2.
Ах, я предположил, что это ошибка. Во всяком случае, это должен быть общий принцип рекурсивного решения. Вы можете выполнить некоторое преобразование переменной индекса, прежде чем использовать ее в строке с оператором for, чтобы получить другой порядок циклов.
Вот обобщенная рекурсивная версия. Он жалуется на непроверенное создание универсального массива в тестовом коде, но сам код перестановки в порядке:
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();
}
}
}
вот мое рекурсивное решение с правильным порядком, основанное на решении Расмуса. он работает, только если все списки имеют одинаковый размер.
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 ...
В некоторой степени вы имитировали то, что рекурсивное решение все равно будет делать (управляя списком индексов). Однако я ожидаю, что ваше решение будет более эффективным, но, возможно, немного менее читаемым, чем рекурсивный эквивалент.