Алгоритм для сопоставления значений одного ключа другим значениям на карте

Question

У меня есть некоторые Карты, которые я хотел бы вычислить декартово произведение. Может кто-то пожалуйста, предложить хороший алгоритм:

данных:

Key1 {100,101,102} 

Key2 {200,201} 

Key3 {300} 

Обязательный выход: (Приказ имеет значение)

100,200,300 
101,200,300 
102,200,300 
100,201,300 
101,201,300 
102,201,300 

Карта является динамическим, так ключ и значения могут изменяться в размер.

Спасибо.

Answer 1

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

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

public class CartesianPrint { 

    public static void main(String[] args) { 
     Map<Integer,List<Integer>> groupMap = new LinkedHashMap<Integer,List<Integer>>(); 

     groupMap.put(1,Arrays.asList(new Integer[]{100,101,102})); 
     groupMap.put(2,Arrays.asList(new Integer[]{200,201})); 
     groupMap.put(3,Arrays.asList(new Integer[]{300})); 

     List<List<Integer>> values = new ArrayList<List<Integer>>(groupMap.values()); 
     int[] printList = new int[values.size()]; 
     print(values,printList,values.size()-1);   
    } 

    static void print(List<List<Integer>> values, int[] printList, int level){ 
     for (Integer value: values.get(level)) { 
      printList[level] = value; 
      if(level == 0){ 
       System.out.println(Arrays.toString(printList)); 
      }else{ 
       print(values,printList,level-1); 
      } 
     }  
    } 

} 

Answer 2

Предлагаю создать магазин кортежей (триплет в вашем примере).

List<List<Integer>> store = new LinkedList(); 

Затем создайте Stack чисел.

Stack<Integer> stack = new Stack(); 

Затем написать рекурсивную функцию:

В каждом вызове рекурсивной функции, нажмите на самом деле обрабатывается значение массива в стек, и добавить текущий кортеж в магазин.

private static process(Iterator<String> keys){ 
    // Bottom-most key 
    if(! keys.hasNext()){ 
     // Construct the tuple from the stack and add it to store. 
    } 
    else { 
     String currentKey = keys.next(); 
     List<Integer> numbers = map.get(currentKey); 
     for(int i : numbers){ 
      stack.push(i); 
      process (keys); 
      stack.pop(); // Dispose processed number. 
     } 
    } 
} 

Надеюсь, я понял проблему правильно (без гарантии). Извините, что не выполнил его целиком, но это ваша домашняя задача :)

Answer 3

То же, что и Ondra Žižka, если вам не нужна карта, возьмите Список, он будет работать одинаково. Это не так оптимизированный способ (я должен клонировать, а не перерасчитывать продукт в рекурсии. Но идея все еще здесь и ее довольно короткая. Я проявлял особую осторожность, чтобы поддерживать правильный порядок, поэтому я просматриваю список назад.

public static List<List<Integer>> getCart(List<List<Integer>> a_list) { 
     List<List<Integer>> l_result = new ArrayList<List<Integer>>(); 
     if (a_list == null || a_list.isEmpty()) { 
      l_result.add(new ArrayList<Integer>()); 
      return l_result; 
     } 
     for (Integer l_value : a_list.get(a_list.size()-1)) { 
      List<List<Integer>> l_resultPortion = getCart(a_list.subList(0, a_list.size() - 1)); 
      for (List<Integer> l_list : l_resultPortion) { 
       l_list.add(l_value); 
      } 
      l_result.addAll(l_resultPortion); 
     } 
     return l_result; 
    }