Самый эффективный способ комбинирования элементов списков элементов в наборах комбинаций?

Question

Предположим, что мы даем список списков некоторых предметов, например строк.

list 1: "a", "b", "c" 

list 2: "d", "e", "f" 

list 3: "1", "2", "3" 


results: (a, d, 1), (a, d, 2), ... (c, f, 3) 

(реальный случай использования не имеет ничего общего со строками и такие, это просто насмешка вверх)

Я написал рекурсивный метод, чтобы сделать это, но я не доволен, потому что это создает много временных наборов, которые меня бросают (да, я знаю, что создание объектов в java дешево, обычно меньше инструкций процессора, чем malloc в C (источник: Java Concurrency in Action, p241), eden GC дешево, бла-бла-бла. Рассмеши меня :).

void combine(List<List<String>> itemLists, List<Set<String>> combinations, Set<String> partial) { 
    if (itemLists == null || itemLists.isEmpty()) return; 
    List<String> items = itemLists.get(0); 
    for (String s : items) { 
     Set<String> tmpSet = new HashSet<>(partial); 
     tmpSet.add(s); 
     if (itemLists.size() == 0) //termination test 
      combinations.add(tmpSet); 
     else 
      combine(itemLists.subList(1, itemLists.size()), combinations, tmpSet); 
    } 
} 

Итак, как бы вы это сделали?

Редактировать: Чтобы быть ясным, я не хочу создавать перестановки. Я хочу создать множество больших размеров (список списков).

Answer 1

Вы хотите, чтобы список всех возможных наборов, содержащих ровно одно значение из каждого из предоставленных списков, предполагал, что количество списков является переменным, а размер этих списков также является переменным. Верный?

Что-то вроде этого, то?

static List<Set<String>> combine(List<List<String>> itemLists) 
{ 
    // Calculate how many combinations we'll need to build 
    int remainingCombinations = itemLists.get(0).size(); 
    for(int i=1; i<itemLists.size(); i++) 
    { 
     remainingCombinations *= itemLists.get(i).size(); 
    } 

    List<Set<String>> allSets = new ArrayList<Set<String>>(); 

    // Generate this combination 
    for (;remainingCombinations > 0; remainingCombinations --) 
    { 
     Set<String> currentSet = new HashSet<String>(); 
     int positionInRow = remainingCombinations; 

     // Pick the required element from each list, and add it to the set. 
     for(int i=0; i<itemLists.size(); i++) 
     { 
      int sizeOfRow = itemLists.get(i).size(); 
      currentSet.add(itemLists.get(i).get(positionInRow % sizeOfRow)); 
      positionInRow /= sizeOfRow; 
     } 

     allSets.add(currentSet); 
    } 
    return allSets; 
} 

Answer 2

Это более эффективно: Подойдите к нему так же, как подсчет работы (каждая «позиция» является один из списков, и каждая «цифра», которая может идти в таком положении элемент в списке):

List<Set<String>> combine(List<List<String>> input){ 

    final int n = input.size(); 
    int[] index = new int[n]; 

    List<Set<Sting>> result = new List<>(); 

    int position = 0; 
    while(position < n){ // "overflow" check 

     // Add set to result. 
     Set<String> set = new HashSet<>(); 
     for(int i=0; i<n; i++) 
      set.add(input.get(i).get(index[i])); 
     result.add(set); 

     // Now the "hard" part: increment the index array 
     position = 0; 
     while(position < n){ 

      if(index[ position ] < input.get(position).size()){ 
       index[position]++; 
       break; 
      } 
      else // carry 
       index[ position++ ] = 0; 
     } 
    } 
    return result; 
} 

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

Answer 3

То, что вы ищете, является «декартовым продуктом».

Если вы используете Сеты вместо списков, вы можете использовать Sets.cartesianProduct. Есть еще некоторый мусор, выделенный, когда вы перебираете результирующие списки ... но не так сильно, как другие подходы.

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

FYI там было a request для Lists.cartesianProduct также, но я не думаю, что кто-то работает над этим.