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

Рейтинг: 0Ответов: 2Опубликовано: 25.11.2014

Доброго времени суток.

Столкнулся с задачей и почему-то никак не могу придумать решение.

Имеются N массивов с разными объектами (каждый массив содержит разные объекты одного типа, какое-то количество), все массивы могут быть разной длины.

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

Т.е. если у нас есть 6 шаров, 4 куба и 3 карандаша (3 массива с 6, 4 и 3-мя элементами), то надо получить массив из 72 элементов, каждый из которых (1-й шар, 1-й куб, 1-й карандаш), (1-й шар, 1-й куб, 2-й карандаш) и т.п., содержащий все возможные перестановки.
Когда массива два, все просто. Но для общего случая я почему-то не могу придумать решение.

Теоретически такое могло бы быть решением:

  1. Перемножаем длины, чтобы узнать результирующее количество.
  2. Создаем результирующий массив получившейся длины.
  3. Далее для i-го элемента мы будем класть шар номер i%6, куб номер i%4, карандаш номер i%3.

Это было бы решением, если бы между 6, 4 и 3 наибольший общий делитель между всеми парами был равен 1, но когда НОД > 1 (например, длины массивов равны и его длина - является НОД-ом), такой вариант не даст перебора всех вариантов. И я совершенно не могу придумать алгоритм, как бы так все перебрать, чтобы каждый с каждым, и без рекурсии. Наверняка же есть какой-то простой и гениальный алгоритм?

алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Пусть массив L содержит длины исходных массивов. Тогда такой код на C++:

vector<int> AbsoluteNumberToIndices(int num)
{
    vector<int> result(L.length);
    for (int index = 0; index < L.length; index++)
    {
        result[index] = num % L[index];
        num /= L[index];
    }
    return result;
}

int IndicesToAbsoluteNumber(const vector<int>& coord)
{
    int num = 0;
    for (int index = L.length; index >= 0; index--)
    {
        num *= L[index];
        num += coord[index];
    }
    return num;
}

пересчитывает набор индексов в массивах в номер от 0 до произведения длин и обратно.

▲ 1

На самом деле, поскольку дело было на пайтоне, то все решилось, как только я нашел itertools.product() (https://docs.python.org/2/library/itertools.html#itertools.product). Но поскольку при внедрении его в существующий код со сложными зависимостями объектов пришлось делать немало костылей, @VladD, Ваше решение мне нравится намного больше, т.к. оно выглядит вживляемым в сложную систему просто. Идея делить после взятия остатка - просто и идеально модернизирует решение, описанное в топике.