0

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

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

Имеются 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 (например, длины массивов равны и его длина - является НОД-ом), такой вариант не даст перебора всех вариантов. И я совершенно не могу придумать алгоритм, как бы так все перебрать, чтобы каждый с каждым, и без рекурсии. Наверняка же есть какой-то простой и гениальный алгоритм?

3
  • 1
    Посмотрите в сторону систем счисления со смешанным основанием.
    – VladD
    Commented 25 нояб. 2014 в 14:42
  • 1
    Почти > i%6, куб номер i%4, карандаш номер i%3. i%6, (i/6)%4, (i/6/4)%3 и т.д. Представьте, что все массивы содержат по 10 элементов. Получите 10-ричную систему счисления. И по номеру i вам надо получить цифры, каждая из которых и будет индексом в соответствующем массиве. Для переменного основания делить надо не на 10, а на число "цифр" в каждом из разрядов - 6,4,3... Commented 25 нояб. 2014 в 14:52
  • С рекурсией же неплохо. Получаете все варианты выборки по 1 элементу из каждого типа. И потом крутите их между собой перестановками.
    – Sergiks
    Commented 25 нояб. 2014 в 15:18

2 ответа 2

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 до произведения длин и обратно.

2
  • Спасибо, идея с первой функцией - то, что нужно. А вот что делает вторая, я не понимаю =) coord - это вектор чего? И зачем мы первым шагом умножаем 0 на L[Index] (если num и result - это одна переменная).
    – Arkady
    Commented 25 нояб. 2014 в 16:55
  • @smallFish: Ой :) Там была опечатка, нужно num. Вторая процедура считает обратное преобразование к первой: по набору индексов общий номер в полной последовательности.
    – VladD
    Commented 25 нояб. 2014 в 17:01
1

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

Ваш ответ

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.