Cartesian 제품을 목록에서 가져 오는 방법

Question

여러 개의 List<T>이 있다고 가정하면 목록> .size()를 호출 할 때까지 내가 가진 목록의 개수를 모를 수 있으므로 다른 목록 (또는 다른 모음)에 넣을 것입니다. 예를 들어 목록 아래

테이크 : 나는 목록 1의 결과를 얻을 수있는 방법

list1=[1,2] 
list2=[3,4] 
list3=[5,6] 
.... 
listn=[2*n-1,2n]; 

* 카티 제품 예를 들어

같은리스트 2 * 목록 3 * ... listn :

list1*list2*list3 should =[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6] 

Answer 1

당신은 그것을 달성하기 위해 재귀를 사용할 수 있습니다. 재귀의 기본 경우는 입력이 비어있는 경우 빈 목록을 반환하고 나머지는 처리합니다. 예 :

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

public class CartesianProduct { 

    public static <T> List<List<T>> calculate(List<List<T>> input) { 
     List<List<T>> res = new ArrayList<>(); 
     if (input.isEmpty()) { // if no more elements to process 
      res.add(new ArrayList<>()); // then add empty list and return 
      return res; 
     } else { 
      process(input, res); // we need to calculate the cartesian product of input and store it in res variable 
     } 
     return res; // method completes , return result 
    } 

    private static <T> void process(List<List<T>> lists, List<List<T>> res) { 
     List<T> head = lists.get(0); //take first element of the list 
     List<List<T>> tail = calculate(lists.subList(1, lists.size())); //invoke calculate on remaining element, here is recursion 

     for (T h : head) { // for each head 
      for (List<T> t : tail) { //iterate over the tail 
       List<T> tmp = new ArrayList<>(t.size()); 
       tmp.add(h); // add the head 
       tmp.addAll(t); // and current tail element 
       res.add(tmp); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     //we invoke the calculate method 
     System.out.println(calculate(Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3, 4), Arrays.asList(5, 6)))); 
    } 
} 

출력 꼬리 재귀를 사용하여 @ sol4me의 대답

[[1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6]] 

Answer 2

덕분에, 여기에 꼬리 재귀를 사용하지 않는 또 다른 버전이다 그러나 나는 이해하기 쉽게라고 생각합니다.

public class CartesianProduct { 

    public static <T> List<List<T>> calculate(List<List<T>> input) { 
     List<List<T>> result= new ArrayList<List<T>>(); 

     if (input.isEmpty()) { // If input a empty list 
      result.add(new ArrayList<T>());// then add empty list and return 
      return result; 
     } else { 
      List<T> head = input.get(0);//get the first list as a head 
      List<List<T>> tail= calculate(input.subList(1, input.size()));//recursion to calculate a tail list 
      for (T h : head) {//we merge every head element with every tail list. 
       for (List<T> t : tail) { 
        List<T> resultElement = new ArrayList<T>(); 
        resultElement.add(h); 
        resultElement.addAll(t); 
        result.add(resultElement); 
       } 
      } 
     } 
     return result; 
    } 


    public static void main(String[] args) { 
     List<List<Integer>> bigList=Arrays.asList(Arrays.asList(1,2),Arrays.asList(3,4),Arrays.asList(5,6),Arrays.asList(7,8)); 
     System.out.println(calculate(bigList)); 
    } 
}