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
    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... 25 ноя 2014 в 14:52
  • С рекурсией же неплохо. Получаете все варианты выборки по 1 элементу из каждого типа. И потом крутите их между собой перестановками.
    – Sergiks
    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
    25 ноя 2014 в 16:55
  • @smallFish: Ой :) Там была опечатка, нужно num. Вторая процедура считает обратное преобразование к первой: по набору индексов общий номер в полной последовательности.
    – VladD
    25 ноя 2014 в 17:01
1

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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