Создание всех комбинаций из нескольких списков

Ответ 1

Вам нужна рекурсия:

Допустим, все ваши списки находятся в lists, который представляет собой список списков. Пусть result будет список ваших необходимых перестановок. Вы можете реализовать это так:

void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
    if (depth == lists.size()) {
        result.add(current);
        return;
    }

    for (int i = 0; i < lists.get(depth).size(); i++) {
        generatePermutations(lists, result, depth + 1, current + lists.get(depth).get(i));
    }
}

Окончательный вызов будет таким:

generatePermutations(lists, result, 0, "");

Ответ 2

Эта тема пригодилась. Я полностью переписал предыдущее решение на Java и стал более удобным для пользователя. Кроме того, для большей гибкости я использую коллекции и дженерики:

/**
 * Combines several collections of elements and create permutations of all of them, taking one element from each
 * collection, and keeping the same order in resultant lists as the one in original list of collections.
 * 
 * <ul>Example
 * <li>Input  = { {a,b,c} , {1,2,3,4} }</li>
 * <li>Output = { {a,1} , {a,2} , {a,3} , {a,4} , {b,1} , {b,2} , {b,3} , {b,4} , {c,1} , {c,2} , {c,3} , {c,4} }</li>
 * </ul>
 * 
 * @param collections Original list of collections which elements have to be combined.
 * @return Resultant collection of lists with all permutations of original list.
 */
public static <T> Collection<List<T>> permutations(List<Collection<T>> collections) {
  if (collections == null || collections.isEmpty()) {
    return Collections.emptyList();
  } else {
    Collection<List<T>> res = Lists.newLinkedList();
    permutationsImpl(collections, res, 0, new LinkedList<T>());
    return res;
  }
}

/** Recursive implementation for {@link #permutations(List, Collection)} */
private static <T> void permutationsImpl(List<Collection<T>> ori, Collection<List<T>> res, int d, List<T> current) {
  // if depth equals number of original collections, final reached, add and return
  if (d == ori.size()) {
    res.add(current);
    return;
  }

  // iterate from current collection and copy 'current' element N times, one for each element
  Collection<T> currentCollection = ori.get(d);
  for (T element : currentCollection) {
    List<T> copy = Lists.newLinkedList(current);
    copy.add(element);
    permutationsImpl(ori, res, d + 1, copy);
  }
}

Я использую библиотеку guava для создания коллекций.

Ответ 3

Эта операция называется декартовым произведением. Для этого в Guava предусмотрена полезная функция: Lists.cartesianProduct

Ответ 4

Без рекурсии уникальные комбинации:

    String sArray[] = new String []{"A", "A", "B", "C"};
    //convert array to list
    List<String> list1 = Arrays.asList(sArray);
    List<String> list2 = Arrays.asList(sArray);
    List<String> list3 = Arrays.asList(sArray);

    LinkedList<List <String>> lists = new LinkedList<List <String>>();

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);

    Set<String> combinations = new TreeSet<String>();
    Set<String> newCombinations;

    for (String s: lists.removeFirst())
        combinations.add(s);

    while (!lists.isEmpty()) {
        List<String> next = lists.removeFirst();
        newCombinations =  new TreeSet<String>();
        for (String s1: combinations) 
            for (String s2 : next) 
              newCombinations.add(s1 + s2);               

        combinations = newCombinations;
    }
    for (String s: combinations)
        System.out.print(s+" ");    

Ответ 5

Добавление ответа, основанного на итераторе, для работы с общим списком списков List<List<T>>, расширяющим идею от Руслана Остафичука. Идея, которой я придерживался, заключалась в следующем:

     * List 1: [1 2]
     * List 2: [4 5]
     * List 3: [6 7]
     * 
     * Take each element from list 1 and put each element 
     * in a separate list.
     * combinations -> [ [1] [2] ]
     * 
     * Set up something called newCombinations that will contains a list
     * of list of integers
     * Consider [1], then [2]
     * 
     * Now, take the next list [4 5] and iterate over integers
     * [1]
     *  add 4   -> [1 4]
     *      add to newCombinations -> [ [1 4] ]
     *  add 5   -> [1 5]
     *      add to newCombinations -> [ [1 4] [1 5] ]
     * 
     * [2]
     *  add 4   -> [2 4]
     *      add to newCombinations -> [ [1 4] [1 5] [2 4] ]
     *  add 5   -> [2 5]
     *      add to newCombinations -> [ [1 4] [1 5] [2 4] [2 5] ]
     * 
     * point combinations to newCombinations
     * combinations now looks like -> [ [1 4] [1 5] [2 4] [2 5] ]
     * Now, take the next list [6 7] and iterate over integers
     *  ....
     *  6 will go into each of the lists
     *      [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] ]
     *  7 will go into each of the lists
     *      [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] [1 4 7] [1 5 7] [2 4 7] [2 5 7]]

Теперь код. Я использовал Set, чтобы избавиться от любых дубликатов. Может быть заменен на List. Все должно работать без проблем.:)

public static <T> Set<List<T>> getCombinations(List<List<T>> lists) {
    Set<List<T>> combinations = new HashSet<List<T>>();
    Set<List<T>> newCombinations;

    int index = 0;

    // extract each of the integers in the first list
    // and add each to ints as a new list
    for(T i: lists.get(0)) {
        List<T> newList = new ArrayList<T>();
        newList.add(i);
        combinations.add(newList);
    }
    index++;
    while(index < lists.size()) {
        List<T> nextList = lists.get(index);
        newCombinations = new HashSet<List<T>>();
        for(List<T> first: combinations) {
            for(T second: nextList) {
                List<T> newList = new ArrayList<T>();
                newList.addAll(first);
                newList.add(second);
                newCombinations.add(newList);
            }
        }
        combinations = newCombinations;

        index++;
    }

    return combinations;
}

Небольшой тестовый блок.

public static void main(String[] args) {
    List<Integer> l1 = Arrays.asList(1,2,3);
    List<Integer> l2 = Arrays.asList(4,5);
    List<Integer> l3 = Arrays.asList(6,7);

    List<List<Integer>> lists = new ArrayList<List<Integer>>();
    lists.add(l1);
    lists.add(l2);
    lists.add(l3);

    Set<List<Integer>> combs = getCombinations(lists);
    for(List<Integer> list : combs) {
        System.out.println(list.toString());
    }

}

Ответ 6

Используйте решение вложенного цикла, предоставленное некоторыми другими ответами, чтобы объединить два списка.

Если у вас более двух списков,

• Объедините первые два в один новый список.
• Объедините полученный список со следующим списком.
• Повтор.

Ответ 7

• Нет рекурсии
• Заказывается
• Можно получить конкретную комбинацию по ее индексу (без создания всех других перестановок):

Метод класса и main() в конце:

public class TwoDimensionalCounter<T> {
    private final List<List<T>> elements;

    public TwoDimensionalCounter(List<List<T>> elements) {
        this.elements = Collections.unmodifiableList(elements);
    }

    public List<T> get(int index) {
        List<T> result = new ArrayList<>();
        for(int i = elements.size() - 1; i >= 0; i--) {
            List<T> counter = elements.get(i);
            int counterSize = counter.size();
            result.add(counter.get(index % counterSize));
            index /= counterSize;
        }
        return result;//Collections.reverse() if you need the original order
    }

    public int size() {
        int result = 1;
        for(List<T> next: elements) result *= next.size();
        return result;
    }

    public static void main(String[] args) {
        TwoDimensionalCounter<Integer> counter = new TwoDimensionalCounter<>(
                Arrays.asList(
                        Arrays.asList(1, 2, 3),
                        Arrays.asList(1, 2, 3),
                        Arrays.asList(1, 2, 3)
                ));
        for(int i = 0; i < counter.size(); i++)
            System.out.println(counter.get(i));
    }
}

Ответ 8

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

Я опубликовал его, так как ни один из ответов здесь не дает четкого алгоритма, и я не могу выдержать рекурсию. Разве мы не находимся в stackoverflow?

String[][] combinations = new String[][] {
                 new String[] { "0", "1" },
                 new String[] { "0", "1" },
                 new String[] { "0", "1" },
                 new String[] { "0", "1" } };

    int[] indices = new int[combinations.length];

    int currentIndex = indices.length - 1;
    outerProcess: while (true) {

        for (int i = 0; i < combinations.length; i++) {
            System.out.print(combinations[i][indices[i]] + ", ");
        }
        System.out.println();

        while (true) {
            // Increase current index
            indices[currentIndex]++;
            // If index too big, set itself and everything right of it to 0 and move left
            if (indices[currentIndex] >= combinations[currentIndex].length) {
                for (int j = currentIndex; j < indices.length; j++) {
                    indices[j] = 0;
                }
                currentIndex--;
            } else {
                // If index is allowed, move as far right as possible and process next
                // combination
                while (currentIndex < indices.length - 1) {
                    currentIndex++;
                }
                break;
            }
            // If we cannot move left anymore, we're finished
            if (currentIndex == -1) {
                break outerProcess;
            }
        }
    }

Выход;

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Ответ 9

Операция, которую вам нужно реализовать, называется Cartesian Product. Для получения дополнительной информации см. Https://en.wikipedia.org/wiki/Cartesian_product

Я рекомендую использовать мою библиотеку с открытым исходным кодом, которая может делать именно то, что вам нужно: https://github.com/SurpSG/Kombi

Пример использования этого метода: https://github.com/SurpSG/Kombi#usage-for-lists-1

Примечание. Библиотека была разработана для высокопроизводительных целей. Вы можете увидеть результаты banchmarks здесь

Библиотека дает вам довольно хорошую пропускную способность и постоянное использование памяти

Ответ 10

Вот пример с использованием битовой маски. Нет рекурсии и нескольких списков

static List<Integer> allComboMatch(List<Integer> numbers, int target) {
    int sz = (int)Math.pow(2, numbers.size());
    for (int i = 1; i < sz; i++) {
        int sum = 0;
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int j = 0; j < numbers.size(); j++) {
            int x = (i >> j) & 1;
            if (x == 1) {
                sum += numbers.get(j);
                result.add(j);
            }
        }
        if (sum == target) {
            return result;
        }
    }
    return null;
}