Генерация всех комбинаций из нескольких списков

Учитывая неизвестное количество списков, каждый с неизвестной длиной, мне нужно создать единый список со всеми возможными уникальными комбинациями. Например, даны следующие списки:

X: [A, B, C] 
Y: [W, X, Y, Z]

Тогда я должен быть в состоянии генерировать 12 комбинаций:

[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

Если был добавлен третий список из 3 элементов, яиметь 36 комбинаций и т. д.

Любые идеи о том, как я могу сделать это на Java?

(псевдокод тоже подойдет)

 AndrewC19 июн. 2013 г., 15:43
Это звучит замечательно, как домашнее задание
 Michael Hillman20 июн. 2013 г., 17:49
Это не былоt, у меня была кратковременная потеря мозгов на работе, так что вместо того, чтобы целую вечность выяснять это самостоятельно, я пришел сюда :)

Ответы на вопрос(10)

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

     * 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  Set getCombinations(List lists) {
    Set combinations = new HashSet();
    Set 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 newList = new ArrayList();
        newList.add(i);
        combinations.add(newList);
    }
    index++;
    while(index < lists.size()) {
        List nextList = lists.get(index);
        newCombinations = new HashSet();
        for(List first: combinations) {
            for(T second: nextList) {
                List newList = new ArrayList();
                newList.addAll(first);
                newList.add(second);
                newCombinations.add(newList);
            }
        }
        combinations = newCombinations;

        index++;
    }

    return combinations;
}

Маленький тестовый блок ..

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

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

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

}

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

static List allComboMatch(List numbers, int target) {
    int sz = (int)Math.pow(2, numbers.size());
    for (int i = 1; i < sz; i++) {
        int sum = 0;
        ArrayList result = new ArrayList();
        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;
}
 Neno Ganchev17 нояб. 2017 г., 22:35
Этот код генерирует суммы всех подмножествnumbers, это не имеет никакого отношения к актуальному вопросу. Он также возвращает индексы элементов, которые складываются в определенную сумму, которая одинаково не связана.

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

Когда у вас есть более двух списков,

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

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

public class TwoDimensionalCounter {
    private final List elements;

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

    public List get(int index) {
        List result = new ArrayList();
        for(int i = elements.size() - 1; i >= 0; i--) {
            List 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 next: elements) result *= next.size();
        return result;
    }

    public static void main(String[] args) {
        TwoDimensionalCounter 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));
    }
}
 bembas07 нояб. 2018 г., 20:23
да, вы правы, я был сбит с толку! Спасибо
 bembas07 нояб. 2018 г., 19:13
Могу ли я спросить, почему вы используете index / = counterSize; ? Потому что это не обязательно.
 Stanislav Bashkyrtsev07 нояб. 2018 г., 19:33
У вас есть три слота, которые могут иметь значения a, b, c, поэтому перестановка начнется с:,aaaaabи т. д. описанная вами операцияАлгоритм сначала сгенерировать 3-ю букву, затем перейти ко 2-й букве и затем перейти к 1-й букве.
Решение Вопроса

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

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

void GeneratePermutations(List Lists, List 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, EmptyString);
 Michael Hillman19 июн. 2013 г., 16:40
После небольшого редактирования, чтобыя работал со списками парных символов (я использовал строки в своем вопросе, так как думал, что это будет легче объяснить), это сработало отлично, спасибо!
 turbo2oh10 апр. 2015 г., 23:42
@armen tsirunyan Было бы сложно изменить это, чтобы сформировать список результатов списков, таких как: [[A, W], [A, X], [A, Y]]?
 Armen Tsirunyan11 апр. 2015 г., 10:28
@ turbo2oh: Для этого потребуется простая модификация программы, просто добавьте запятые и скобки, где вы хотите.
 Shessuky29 июн. 2018 г., 12:19
Он тестировался: с 2, 3 и 4 списками строк, он работал довольно хорошо ... большое спасибо!
 James Montagne19 июн. 2013 г., 15:55
Это был в основном яваиш. Я удалил String.add и String.removeLastCharacter, но при этом немного изменил вашу логику (надеюсь, к лучшему). Не стесняйтесь вернуться.

Эта тема пригодилась. Я'Мы переписали предыдущее решение полностью на 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.
 * 
 * Example
 * Input  = { {a,b,c} , {1,2,3,4} }
 * 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} }
 * 
 * 
 * @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  Collection permutations(List collections) {
  if (collections == null || collections.isEmpty()) {
    return Collections.emptyList();
  } else {
    Collection res = Lists.newLinkedList();
    permutationsImpl(collections, res, 0, new LinkedList());
    return res;
  }
}

/** Recursive implementation for {@link #permutations(List, Collection)} */
private static  void permutationsImpl(List ori, Collection res, int d, List 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 currentCollection = ori.get(d);
  for (T element : currentCollection) {
    List copy = Lists.newLinkedList(current);
    copy.add(element);
    permutationsImpl(ori, res, d + 1, copy);
  }
}

используя библиотеку гуавы для создания коллекций.

 jDub925 янв. 2018 г., 15:39
Этот код мне очень помогает. Я ценю это, но могу ли я знать, почему вы используете Lists.newLinkedList вместо List <T> copy = new LinkedList <>(); эта версия более эффективна. Я все еще вижу, как я писал выше, используется чаще.
 Víctor29 янв. 2018 г., 11:34
Оператор diamond не был доступен в той версии JDK, которую я использовал в то время, поэтому я использовал эти фабричные классы (такие как списки, наборы или карты) только для удобства и ясности кода. Они не более эффективны или что-то в этом роде.

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

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

    LinkedList lists = new LinkedList();

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

    Set combinations = new TreeSet();
    Set newCombinations;

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

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

        combinations = newCombinations;
    }
    for (String s: combinations)
        System.out.print(s+" ");    
 rliu20 июн. 2013 г., 19:00
Ах тыверно. Его пример заставил меня думать, что он невсе равно, так как он сказал "если мы добавим третий список длиной 3, тогда будет 36 " который нене обязательно верно, если вы заботитесь об уникальности. Ну что ж, +1уже
 Ruslan Ostafiichuk20 июн. 2013 г., 08:19
Он сказал "все возможные уникальные комбинации ", Результат будетААА, ААА, АБА ... » в моем случае {"A", "A", "B", "C"} после использования списков вместо наборов.
 rliu19 июн. 2013 г., 19:17
Я нене думаю, что ты хочешьcombinations а такжеnewCombinations бытьSets. Он неНе указывайте какие-либо ограничения уникальности. Я бы просто сделал их обоихListи тогда я верю, что это работает.

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

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

Вот пример, как его использовать:https://github.com/SurpSG/Kombi#usage-for-lists-1

Заметка: Библиотека была разработана длявысокая производительность цели. Вы можете наблюдать результаты бенчмарковВот

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

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

 Drakes10 июн. 2018 г., 05:20
Лучший ответ, если вы уже используете гуаву

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

Я опубликовал его, поскольку ни один из ответов не дает четкого алгоритма, и я могут рекурсия. Мы не напереполнение стека в конце концов?

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

Ваш ответ на вопрос