Рассмотрим массив массивов.
[[“A”,”B”,”C”],[“D”,”E”],[“F”,”G”]
Давайте назовем этот массив нашим исходным массивом. Мы начнем с рассмотрения того, сколько всего комбинаций возможно, используя наш исходный массив. 0-й подмассив имеет 3 элемента на выбор, 1-й — 2, а 2-й — 2. Небольшие математические вычисления показывают, что существует 3*2*2 = 12 возможных комбинаций. Пока достаточно легко.
Теперь, как нам гарантировать, что мы получим 12 уникальных массивов? Рассмотрим массив из 12 пустых массивов. Мы будем обновлять это по мере продвижения, пока не получим массив всех возможных комбинаций, и мы будем ссылаться на него как на наш окончательный ответ в будущем.
Все эти массивы в нашем финальном массиве идентичны; это просто пустые массивы. Давайте посмотрим на самый первый элемент в нашем исходном подмассиве ["A", "B", "C"] и на то, как он должен отображаться в нашем списке конечных массивов. Имеет смысл, что каждый элемент в нем должен появляться одинаковое количество раз, так как ни один из них не повторяется. Таким образом, мы распределили бы их поровну: запихнули бы каждый элемент в 1/3 массива, чтобы у нас было 4 массива, начинающихся с «А», 4 массива, начинающихся с «В», и так далее. Начало кажется достаточно простым. Наш окончательный массив выглядит так:
[[“A],
[“A”],
[“A”],
[“A”],
[“B”],
[“B”],
[“B”],
[“B”],
[“C”],
[“C”],
[“C”],
[“C”]]
Теперь давайте рассмотрим второй элемент в нашем исходном массиве. У нас есть 3 уникальных массива в нашем окончательном ответе прямо сейчас и 2 элемента в подмассиве, который мы добавляем. Как и в прошлый раз, каждый элемент должен появляться одинаковое количество раз. Мы можем определить количество раз, которое он отображается с точки зрения переменных: мы будем помещать каждый элемент в конечный массив всего (длина конечного массива) / (длина подмассива) раз. В этом случае: 12/ 2 = 6 раз.
Таким образом, каждый элемент подмассива появляется 6 раз. Но как нам убедиться, что каждая из этих 6 попыток находится в правильном месте? Давайте снова рассмотрим количество уникальных элементов, представленных в нашем окончательном массиве. У нас есть 3 уникальных элемента. Каждый из них должен получить равное количество входящих элементов. Из 6 копий каждого входящего элемента 1/3 должна попасть в массивы, начинающиеся с «А», 1/3 должны уйти в массивы, начинающиеся с «В» и т. д. Напомним, что на данный момент у нас есть 3 уникальных массива в нашем финальном массиве .
Таким образом, окончательная формула для того, сколько раз новый элемент должен появиться в уникальном элементе: 1/(количество уникальных элементов в конечном массиве) * (длина конечного массива)/(длина подмассива, который мы помещаем ). Применяя это к нашему текущему примеру, мы получаем 1/3 * 12/2 = 2. Таким образом, каждый элемент будет помещен в каждый уникальный массив 2 раза. Наш окончательный массив в настоящее время выглядит так:
[[“A”,”D”],
[“A”,”D”],
[“A”,”E”],
[“A”,”E”],
[“B”,”D”],
[“B”,”D”],
[“B”,”E”],
[“B”,”E”],
[“C”,”D”],
[“C”,”D”],
[“C”,”E”],
[“C”,”E”]]
Давайте теперь рассмотрим последний элемент нашего исходного массива ["F", "G"]. Мы не собираемся делать ничего нового с этим элементом — мы просто будем продолжать делать то, что уже сделали.
Шаг 1) Давайте выясним, сколько уникальных массивов у нас есть в нашем окончательном массиве прямо сейчас. Подсчитав их, мы видим, что у нас есть 6 уникальных элементов.
Шаг 2) Давайте посмотрим, сколько элементов в нашем входящем массиве. У нас есть в общей сложности 2; «Ф» и «Г».
Шаг 3) Давайте воспользуемся нашей предыдущей формулой, чтобы определить, сколько раз каждый элемент должен отображаться на каждом уникальном элементе. Это 1/(количество уникальных элементов в конечном массиве) * (длина конечного массива)/(длина подмассива, который мы помещаем) или 1/(6) * 12/2 = 1. Таким образом, каждый элемент из конечного массива должен идти по каждому уникальному элементу ровно один раз. Наш окончательный массив, наконец, будет выглядеть так:
[[“A”,”D”,”F”],
[“A”,”D”,”G”],
[“A”,”E”,”F”],
[“A”,”E”,”G”],
[“B”,”D”,”F”],
[“B”,”D”,”G”],
[“B”,”E”,”F”],
[“B”,”E”,”G”],
[“C”,”D”,”F”],
[“C”,”D”,”G”],
[“C”,”E”,”F”],
[“C”,”E”,”G”]]
И вот оно — программный взгляд на то, как разделить массив массивов на все его возможные уникальные комбинации. Хотите увидеть код, который позаботится об этом за вас? Вы можете найти его в JavaScript на моем github! Спасибо за чтение!
