Как найти все возможные комбинации элементов

Как получить все возможные комбинации элементов группы массивов

Знаю что эту задачу многие гуглят, т.к. сам недавно столкнулся с этим. Поскольку рабочего решения я так и не нашел, пришлось придумать свое.

Итак, вводные данные. Имеем группу массивов, например:

models = [ "audi", "bmw", "toyota", "vw" ];
colors = [ "red", "green", "blue", "yellow", "pink" ];
engines = [ "diesel", "gasoline", "hybrid" ];
transmissions = [ "manual", "auto", "robot" ];

Теперь представим, что нам надо собрать набор ассоциативных массивов (map) примерно такого вида:

variant1 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "manual" }
variant2 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "auto" }
variant3 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "robot" }
variant4 = { "model": "audi", "color": "red", "engine": "gasoline", "transmission": "manual" }
…
variantN = { "model": "vw", "color": "pink", "engine": "hybrid", "transmission": "robot" }

В упрощенном виде алгоритм подобной работы выглядит так:

for(i1 = 0; i1 < models.length; i1 ++){ //Перебираем все модели
    for(i2 = 0; i2 < colors.length; i2 ++){ //Перебираем все возможные цвета
        for(i3 = 0; i3 < engines.length; i3 ++){ //Перебираем все типы двигателей
            for(i4 = 0; i4 < transmissions.length; i4 ++){ //Перебираем все типы трансмиссий
                 variant = {
                      "model": models[i1],
                      "color": colors[i2],
                      "engine": engines[i3],
                      "transmission": transmissions[i4],
                 }
            }
        }
    }
} 

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

Для начала определимся с терминами:

Параметр — то, как называется элемент набора, например model, color и т.д.
Набор элементов параметра — список, присвоенный параметру (например, [ «audi», «bmw», «toyota», «vw» ])
Элемент набора — отдельный элемент списка, например audi, bmw, red, blue и т.п.
Итоговые наборы — то что мы должны сгенерировать

Как это будет выглядеть? Нам потребуется функция, при каждом вызове которой будет сдвигаться на одну позицию условный счетчик итератора, контролирующего перебор параметров (model, color и т.п.). Внутри этой функции помимо сдвига счетчика будет проходить перебор элементов параметра (audi, bmw…; red, blue… и т.д.). И внутри этого вложенного цикла наша функция будет рекурсивно вызывать сама себя.

Далее рабочий пример на языке Java с комментариями:

public class App {

    public static void main(String[] args) {
        Map<String, List<String>> source = Map.of(
            "model", Arrays.asList("audy", "bmw", "toyota", "vw"),
            "color", Arrays.asList("red", "green", "blue", "yellow", "pink"),
            "engine", Arrays.asList("diesel", "gasoline", "hybrid"),
            "transmission", Arrays.asList("manual", "auto", "robot")
        );

        Combinator<String, String> combinator = new Combinator<>(source);
        List<Map<String, String>> result = combinator.makeCombinations();

        for(Map variant : result){
            System.out.println(variant);
        }
    }

    public static class Combinator<K,V> {

        //Тут в виде ассоциативного массива хранятся исходные данные
        private Map<K, List<V>> sources;

        //Итератор для перебора параметров. В нашем случае это обязательно
        //ListIterator, т.к. потребуется вызывать метод previous
        private ListIterator<K> keysIterator;

        //Счетчик текущего положения в итерации для каждого параметра
        //где ключ - имя параметра, а значение - текущая позиция в наборе элементов
        private Map<K, Integer> counter;

        //Тут будут храниться итоговые наборы
        private List<Map<K,V>> result;


        public Combinator(Map<K, List<V>> sources) {
            this.sources = sources;
            counter = new HashMap<>();
            keysIterator = new ArrayList<>(sources.keySet())
                    .listIterator();
        }

        //Этот метод вызываем для генерации набора
        public List<Map<K,V>> makeCombinations() {
            result = new ArrayList<>();
            //Запускаем перебор параметров
            loop();
            return result;
        }

        private void loop(){
            //Проверяем, есть ли еще параметры в источнике
            if(keysIterator.hasNext()){

                //Сдвигаем счетчик вперед
                K key = keysIterator.next();

                //Активируем набор элементов (указываем в счетчике,
                //что находимся на первом элементе набора)
                counter.put(key, 0);


                //Перебираем элементы набора
                while(counter.get(key) < sources.get(key).size()){
                    //Рекурсивно вызываем метод loop чтобы активировать следующий набор элементов
                    loop();

                    //Сдвигаем счетчик элементов набора
                    counter.put(key, counter.get(key) + 1);
                }

                //Если мы уже перебрали элементы набора - сдвигаем итератор параметров назад
                keysIterator.previous();
            }
            else{
                //Если параметров в источнике нет, т.е. мы активировали все наборы попеременно
                //заполняем очередной итоговый набор
                fill();
            }
        }

        //В этом методе наполняем очередной итоговый набор
        private void fill() {
            Map<K,V> variant = new HashMap<>();

            //Перебираем все параметры
            for(K key : sources.keySet()){
                //Получаем значение текущего элемента в наборе
                Integer position = counter.get(key);

                //Вставляем в итоговый набор
                variant.put(key, sources.get(key).get(position));
            }

            result.add(variant);
        }

    }

}

Перестановки

Перестановки – это комбинации изначального массива, получаемые перестановкой элементов. Количество перестановок An = n! Алгоритм получения перестановки по номеру (1..n!) таков:

Смысл заключается в том, что мы на каждой итерации берем элемент из массива и убираем его, переходя к следующей итерации, имеем массив меньшей длины… и так продолжаем пока исходный массив не опустеет. При этом номер комбинации получается исходя из порядка вынимания элементов массива. Аналогичный подход используется в алгоритме Фишера–Йетса для перемешивания массива, только там элемент, который будет выбран на каждой итерации берется случайным образом.

Сочетания

Сочетания – это наборы определенной длины (k), составленные из множества определенной длины (n). Сочетания, в которых одни те же элементы поменены местами, считаются одним сочетанием, поэтому для удобства берутся те сочетания, элементы в которых упорядочены по возрастанию (в лексикографическом порядке). Количество сочетаний C(n,k) – читается как “Це из эн по ка”, = n!/(k!(n-k)!), называются биномиальными коэффициентами. Алгоритм получения сочетания по номеру таков:

Номер сочетания берется как сумма всех биномиальных коэффициентов для массивов уменьшающейся длины (на самом деле сформулировать кратко и притом понятно принцип нумерации сложно, ссылка на теорию будет ниже).

Размещения

Сочетания и перестановки являются частными случаями размещений.
Размещения – это сочетания, где важен порядок элементов. Или, другими словами, это перестановки сочетаний. Количество размещений A(n,k)=k!*C(n,k)=n!/(n-k)!.
Таким образом, чтоб получить размещение по номеру, делим общее количество размещений на цело на номер – получаем номер сочетания, и применяем к нему перестановку с номером как остаток от деления количества размещений на номер размещения.

Размещения с повторениями

Отдельным вариантом комбинации является размещение с повторением. A'(n,k) = n^k. Т.е. все варианты массивов длины k, где на каждой позиции может быть любой элемент из множества размера n. Самый простой для понимания вариант – это A(10,k) – все десятичные числа от 0 до 10^k-1. Или A(2,k) – все двоичные числа длины k.
Нумерация элементов натуральная, индекс комбинации соответствует десятичному аналогу числа в n-ричной системе счисления.

См. также

Про нумерацию размещений и сочетаний можно почитать в статье “О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем” (гуглится), алгоритмы приведены оттуда, ссылки в статье ведут на:

• Дейкстра Э. Дисциплина программирования.
• Липский В. Комбинаторика для программистов.

Оптимизация

Поскольку расчеты ведутся с использованием факториалов, то для больших значений n,k скорее всего может потребоваться длинная арифметика. В то же время вполне возможно, что точное вычисление факториала не понадобится (надо проверять), и достаточно будет формулы Стирлинга… В приведенных алгоритмах функция факториала написана для простоты понимания.

Обратная задача

Каждый из вариантов комбинаций может иметь обратную задачу – получение номера по комбинации. Имея представление о принципе нумерации обратная задача также решается. Например, для размещений с повторениями – это перевод n-ричной системы счисления в десятичную…

Использование

Имея рассчитанные значения факториалов или вообще таблиц со всеми комбинациями определенного типа есть возможность получения случайной комбинации с использованием только одного вызова ГСЧ для получения комбинации.

Как получить все возможные комбинации элементов в Python?

Наиболее эффективный способ получить все возможные комбинации элементов в Python — это использовать модуль itertools и входящую в него функциию permutations().

Почему стоит использовать модуль itertools?

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

Синтаксис функции permutations()

import itertools 
itertools.permutations(lst, length = None) 

Параметрами функции являются:

• lst — это итерируемая последовательность (например: список, кортеж, строка)
• lengh — это длина возвращаемых кортежей (необязательный параметр). Если length = None, то для перестановок будут использоваться все элементы итератора.

Ниже мы рассмотрим варианты получения всех возможных перестановок для списка и строки:

• Получим все перестановки элементов списка lst = [1, 2, 3]
• Получим все возможные сочетания букв в слове «кот»
• Получим комбинации из двух элементов списка lst = [1, 2, 3]
• Получим сочетания из двух букв слова «кот»

Код для получения всех комбинаций элементов в Python
(длина комбинаций = числу элементов)

1. Получим все перестановки элементов списка lst = [1, 2, 3]:

import itertools
 
nums = [1, 2, 3]
permutations = list(itertools.permutations(nums))
print(permutations)

Вывод на экран:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)] 

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

2. Получим все возможные сочетания букв в слове «кот»:

import itertools

word = "кот"
# получим списки из перестановок букв
letters = list(itertools.permutations(word))
# объединим списки с буквами в слова
permutations = [ ''.join(i) for i in letters ]

print(permutations)

Вывод на экран:

['кот', 'кто', 'окт', 'отк', 'тко', 'ток'] 

Пояснения к коду:

С помощью кода list(itertools.permutations(word)) мы получаем список с кортежами из букв «к», «о» и «т», расположенных в разном порядке:

letters = [('к', 'о', 'т'), ('к', 'т', 'о'), ('о', 'к', 'т'), ('о', 'т', 'к'), ('т', 'к', 'о'), ('т', 'о', 'к')].

Так как мы получаем комбинации, содержащие все три буквы слова «кот», значение второго аргумента для функции permutations() можно не указывать. Теперь чтобы объединить кортежи из букв в слова, для каждого кортежа i из списка letters вызовем метод ''.join(i), объединяющий кортеж в строку. Вместо генератора списков permutations = [ ''.join(i) for i in letters ] можно организовать перебор элементов списка letters с помощью цикла for. Это также рабочий способ, хоть и более динный:

import itertools

word = "кот"
# получим списки из перестановок букв
letters = list(itertools.permutations(word))
permutations = []
for i in letters:
    permutations.append(''.join(i))
print(permutations)

Вывод на экран:

['кот', 'кто', 'окт', 'отк', 'тко', 'ток']

Код для получения комбинаций из n элементов:
(длина комбинаций < числа элементов итератора)

1. Получим комбинации из двух элементов списка lst = [1, 2, 3] :

import itertools

lst = [1, 2, 3]
res = list(itertools.permutations(lst, 2))
print(res)

Вывод на экран:

[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

Пояснения к коду: так как нам нужно получить комбинации из двух элементов списка lst, то в качестве второго аргумента функции permutation() мы передаем значение 2.

2. Получим сочетания из двух букв слова «кот»:

import itertools

word = "кот"
letters = list(itertools.permutations(word, 2))
res = [''.join(i) for i in letters]
print(res)

Вывод на экран:

['ко', 'кт', 'ок', 'от', 'тк', 'то'] 

Пояснения к коду:

Так как мы получаем комбинации двух букв слова «кот», то в качестве второго аргумента функции permutations() передаем значение 2.

В результате выполнения кода: list(itertools.permutations(word, 2)) мы получим список letters, состоящий из кортежей: [('к', 'о'), ('к', 'т'), ('о', 'к'), ('о', 'т'), ('т', 'к'), ('т', 'о')]. После этого мы объединяем элементы кортежей в строки с помощью метода ''.join(i). Метод join() будем вызывать для каждого кортежа, входящего в letters. Объединение букв — элементов кортежей можно также организовать в цикле for. Тогда код будет выглядеть немного иначе:

import itertools

word = "кот"
letters = itertools.permutations(word, 2)

res = []
for i in letters:
    res.append(''.join(i))
print(res)

Вывод на экран:

['ко', 'кт', 'ок', 'от', 'тк', 'то'] 

У нас появился Telegram-канал для изучающих Python! Присоединяйтесь: вместе «питонить» веселее! 😉 Ссылка на канал: «Кодим на Python!»

Это история об информатике, алгоритмах и понимании мощи компьютеров. 

Представим такую ситуацию: компания по продаже компьютеров хочет написать самую эффективную рассылку для своих клиентов. Маркетологи сказали, что в письме обязательно должно быть 4 блока:

Но никто не знал, в каком порядке лучше всего расположить эти блоки, чтобы рассылка сработала максимально круто. В итоге решили перебрать все комбинации и отправить много разных рассылок. Для этого позвали программиста, который написал для них простой скрипт — он выводит все варианты расположения блоков. Сегодня мы попробуем это повторить.

О чём речь

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

Таких вариантов можно составить 4! («четыре факториал») — то есть 24 штуки. Восклицательный знак означает факториал, то есть нам нужно перемножить все числа от 1 до этого числа:

4! = 1 × 2 × 3 × 4 = 24

Получается, из четырёх блоков можно сделать 24 разных варианта письма. Вручную перебирать их все сложно, да и нет смысла: компьютер с этим справится гораздо быстрее. Для этого и сделаем алгоритм.

В чём идея

Чтобы перебрать все варианты, можно сделать так:

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

А можно подойти к вопросу иначе:

Обратите внимание, что у нас получился только один цикл, который перебирает по очереди все элементы массива. А вот внутри этого цикла и происходит вся магия: мы погружаемся всё глубже и глубже по одним и тем же правилам, а потом начинаем собирать результаты с конца. 

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

Почему рекурсия лучше вложенных циклов

Когда вложенных циклов мало, то с ними проще: можно контролировать всё вручную. А вот когда циклов становится не три, а 10 или 50, то сильно вырастает вероятность ошибиться в переменной или забыть про какое-то условие. В рекурсии такой проблемы нет: мы один раз описываем, как нырнуть и как оттуда вынырнуть, и всё, остальное компьютер сделает сам.

Ещё бывает такое, что мы заранее не знаем, сколько будет блоков для перестановок — 4 или 40, например. Рекурсия здесь тоже выигрывает: достаточно в одном цикле перебрать все элементы массива, а дальше всё сработает само.

Так и сделаем.

Алгоритм

Единственное, что нам понадобится нового для рекурсии, о чём мы ещё не говорили, — это мемоизация. 

В программировании мемоизацией называют временное хранение промежуточных результатов вычислений, чтобы не вычислять их по сто раз. Один раз посчитал, добавил в переменную-кеш — и отлично.

В нашем случае за это будет отвечать такая строчка:

var memo = memo || [];

Она появляется в самом начале рекурсии и означает вот что:

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

Теперь смотрите код и читайте комментарии:

var email = ['скидка', 'анонс', 'популярное', 'рассказ'];

// массив для результатов перестановок
var results = [];

// рекурсивная функция
// на вход получает текущий массив и массив с памятью предыдущих вычислений
function permute(arr, memo) {
  // переменная для хранения фрагмента массива
  var cur;

  // делаем переменную для хранения промежуточных результатов
  // в программировании это называется «мемоизация»
  var memo = memo || [];

  // какой размер входного массива — такой длины и делаем цикл, чтобы перебрать все элементы
  for (var i = 0; i < arr.length; i++) {

    // получаем новый массив cur, удаляя из входного массива один элемент, начиная с текущей позиции
    // при этом из входного массива этот элемент тоже удалится
    cur = arr.splice(i, 1);

    // если от входного массива ничего не осталось
    if (arr.length === 0) {
      // то приклеиваем текущее значение нарезки к варианту, который лежит в памяти, 
      // и добавляем получившийся результат в итоговый массив
      results.push(memo.concat(cur));
    }

    // вызываем новый виток рекурсии
    // в качестве аргументов передаём копию входящего массива и добавляем к кешу памяти то, что получилось после удаления одного символа из входящего массива
    permute(arr.slice(), memo.concat(cur));

    // возвращаем в исходный массив первый элемент из нового массива, но уже на другую позицию
    arr.splice(i, 0, cur[0]);
  }

  // возвращаем обратно массив с результатами перестановок
  return results;
}

permute(email);

Запустим код в консоли браузера:

Видно, что мы получили 24 перестановки, как и должно было быть. Они все разные, ни в одной нет повторений — то, что нам нужно. Теперь можно отдать эти последовательности дальше, чтобы по каждой из них собрали своё письмо для клиентов.

Если интересно, как рекурсия справится со сложными вариантами и сколько их получится, — сделайте в исходном массиве в коде не 4, а 10 элементов.

Что дальше

Попробуем использовать этот же подход в задаче коммивояжёра — там тоже есть много вложенных циклов. Должно сработать.

Перестановки и комбинации набора элементов в Python – это различные расположения элементов набора:

• Комбинация – это набор элементов, порядок которых не имеет значения.
• Перестановка – это расположение набора, в котором порядок имеет значение.

Рассмотрим набор как:

{A, B, C}

Перестановки вышеуказанного набора следующие:

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

Комбинации вышеуказанного набора, когда два элемента взяты вместе, следующие:

('A', 'B')
('A', 'C')
('B', 'C')

В этом руководстве мы узнаем, как получить перестановки и комбинации группы элементов в Python. Мы рассмотрим наборы символов и цифр.

Мы будем использовать методы combinations() и permutations() в модуле itertools.

Перестановки числовых данных

Чтобы использовать метод permutations() в модуле itertools, нам сначала нужно импортировать модуль.

import itertools

Теперь давайте определим набор чисел.

val = [1, 2, 3, 4]

Теперь, чтобы получить список перестановок, воспользуемся методом permutations().

perm_set = itertools.permutations(val)

Строка кода выше дает объект itertools. Чтобы напечатать различные перестановки, мы будем перебирать этот объект.

for i in perm_set:
    print(i)

Мы получаем результат как:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Полный код этого раздела приведен ниже:

import itertools
 
val = [1, 2, 3, 4]
 
perm_set = itertools.permutations(val)
 
for i in perm_set:
    print(i)

Перестановки строки

Далее мы узнаем, как получить перестановки символов в строке.

Мы будем использовать метод permutations(), но на этот раз мы передадим строку в качестве аргумента.

import itertools
 
s = "ABC"

perm_set = itertools.permutations(s)
for val in perm_set:
    print(val)

Вывод :

('A', 'B', 'C')
('A', 'C', 'B')
('B', 'A', 'C')
('B', 'C', 'A')
('C', 'A', 'B')
('C', 'B', 'A')

Перестановки фиксированной длины

Мы можем найти перестановки набора, в котором мы берем только указанное количество элементов в каждой перестановке. Это похоже на nPr в области математики.

Код для поиска перестановок фиксированной длины приведен ниже:

import itertools
 
val = [1, 2, 3, 4]
 
perm_set = itertools.permutations(val,2)
 
for i in perm_set:
    print(i)

Вывод :

(1, 2)
(1, 3)
(1, 4)
(2, 1)
(2, 3)
(2, 4)
(3, 1)
(3, 2)
(3, 4)
(4, 1)
(4, 2)
(4, 3)

Комбинации числовых данных

Так же, как метод permutations(), мы можем использовать combinations() также в itertools для получения комбинаций набора.

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

import itertools
 
val = [1, 2, 3, 4]
 
com_set = itertools.combinations(val, 2)
 
for i in com_set:
    print(i)

Вывод :

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

Комбинации строки

Мы также можем получить комбинации строки. Используйте следующий фрагмент кода:

import itertools
 
s = "ABC"
 
com_set = itertools.combinations(s, 2)
 
for i in com_set:
    print(i)

Вывод :

('A', 'B')
('A', 'C')
('B', 'C')

Комбинации с заменами

В модуле itertools есть еще один метод, который называется комбинациями_with_replacement(). Этот метод также учитывает комбинацию числа с самим собой.

Посмотрим, как это работает.

Для числового набора

import itertools
 
val = [1, 2, 3, 4]
 
com_set = itertools.combinations_with_replacement(val, 2)
 
for i in com_set:
    print(i)

Вывод :

(1, 1)
(1, 2)
(1, 3)
(1, 4)
(2, 2)
(2, 3)
(2, 4)
(3, 3)
(3, 4)
(4, 4)

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

Для строки

import itertools
 
val = "ABCD"
 
com_set = itertools.combinations_with_replacement(val, 2)
 
for i in com_set:
    print(i)

Вывод :

('A', 'A')
('A', 'B')
('A', 'C')
('A', 'D')
('B', 'B')
('B', 'C')
('B', 'D')
('C', 'C')
('C', 'D')
('D', 'D')