java - recursivo - recursividad en lugar de multi-loops

recursividad potencia java

Question

Quiero que este método funcione para una cantidad determinada de argumentos, puedo hacerlo con la generación de código (con un montón de código feo), ¿se puede hacer con recursividad? ¿si es así, cómo? Entiendo la recursión, pero no sé cómo escribir esto.

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);
            }
        }
    }
}

Answer 1

¿Necesitas que sea recursivo? Lo haría no recursivo, pero aún así no es un caso especial:

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;
}

Answer 2

Aquí hay una implementación recursiva simple:

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);
    }
  }
}

Answer 3

Aquí hay una versión recursiva generalizada. Se queja de la creación de matriz genérica no comprobada en el código de prueba, pero el código permute está bien:

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();
        }
    }
}

Answer 4

esta es mi solución recursiva con un orden correcto, basado en la solución de Rasmus. solo funciona si todas las listas son del mismo tamaño.

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;
            }
        }

}

una solución de "ordenamiento correcto" que permita listas de diferentes tamaños tendrá que comenzar desde la última lista y trabajar hasta la primera lista (listas [0]), añadiendo el elemento al principio o al final de la cadena "pre" y pasarlo hacia adelante. de nuevo, la primera lista imprimirá el resultado. Hubiera codificado eso, pero el almuerzo está listo y a la novia le empieza a gustar el ...