Составление комбинаций из элементов списков

Тема в разделе "WASM.A&O", создана пользователем cryptic_elk, 27 апр 2011.

  1. cryptic_elk

    cryptic_elk New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2009
    Сообщения:
    25
    Пусть имеется k списков произвольного типа с различным количеством элементов.
    Напр.:
    x1=["one","two","three"]
    x2=[1,2,3,4,5]
    x3=[234,543,12555,521,22]
    ...

    Нужнен алгоритм перебора значений всех этих списков и составления комбинаций из этих значений
    Пр.:
    ["one",1,234]
    ["one",2,234]
    ...

    Пните меня, пожалуйста, в сторону матчасти, позволяющей реализовать данную задачу эффективно
     
  2. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    cryptic_elk
    делаеш "к" количество вложенных циклов, с количеством итераций - равных размеру каждого списка,
    а в центральном цикле составляешь результат из данных списков из элементов с индексами циклов.
    как-то так ..
     
  3. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    wsd
    А если k вводится с клавиатуры?

    Тут есть два варианта. Либо рекурсия, либо массив итераторов (индексов) по массивам. Рекурсия проще. Функция выполняет цикл перебирая элементы одного массива, и на каждой итерации цикла вызывает сама себя передавая в качестве, чуть меньше массивов (на один меньше), и начало текущей комбинации. Массив же индексов... Там тоже в общем ничего сложного нет, но лень объяснять.
     
  4. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    На случай, если кто-то вдруг решил, что варианта всего два. Уж не знаю, проще ли рекурсия, а обойтись можно ровно одним циклом, перебирающим натуральные числа, и отображением натурального числа на комбинацию. Отображение может выглядеть таким образом:
    Код (Text):
    1. //num — (на входе) число, которое хотим отобразить
    2. //combination — (на выходе) массив, представляющий собой комбинацию (индексов в списках)
    3. //listLen — (на входе) массив, содержащий размеры списков
    4. //listCount — (на входе) длина массива listLen и соответственно массива combination
    5. void FillCombination(DWORD num, DWORD *combination, DWORD *listLen, DWORD listCount)
    6. {
    7.     DWORD prod = 1;
    8.     for (DWORD i = 0; i < listCount; i++)
    9.         prod *= listLen[i];
    10.     for (DWORD i = 0; i < listCount; i++)
    11.         prod /= listLen[i], combination[i] = num/prod, num %= prod;
    12. }
    Тогда перебрать комбинации можно одним простым циклом:
    Код (Text):
    1. const int LIST_SIZE = 3;
    2. DWORD listLen[LIST_SIZE] = {3,37,5}, combination[LIST_SIZE];
    3. for (DWORD i = 0; i < 3*37*5; i++)
    4. {
    5.     //получаем комбинацию
    6.     FillCombination(i, combination, listLen, LIST_SIZE);
    7.     //Выводим комбинацию
    8.     for (DWORD j = 0; j < LIST_SIZE; j++) printf("%2d ", combination[j]);
    9.     printf("\n");
    10. }
    Разумеется, глупо каждый раз внутри FillCombination вычислять prod. В данном случае это сделано для наглядности.
     
  5. cryptic_elk

    cryptic_elk New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2009
    Сообщения:
    25
    Огромное спасибо всем за ответы
     
  6. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.473
    Адрес:
    Russia
    Если по-русски, то у тебя есть трёхзначное число, где первая цифра - из интервала х1, вторая - из х2, третья - из х3. В общем случае стоило бы соорудить массив из трёх элементов, каждый из которого представляет разряд числа, и делать инкремент этого числа, после этого проверяя переполнение в каждом разряде и при необходимости выполняя перенос. Как только возникнет перенос в 3 разряде - процесс прекратить. Для списков с суммарным числом вариантов меньше 2^32 (или 2^64 с небольшими модификациями) можно использовать код l_inc.
     
  7. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    l_inc
    Это вариант с массивом итераторов. Который CyberManiac описал чуть более подробно. У тебя в качестве массива итераторов выступает массив combination.
    Единственное что, я бы не стал заниматься маппингом int'а в вектор итераторов. Все эти деления и остатки от деления лишь ужасно тормозят код. Быстрее и проще будет впрямую "инкрементировать" вектор итераторов.

    Так что, доказательство того, что вариантов больше двух не зачитывается. ;)
     
  8. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    CyberManiac
    Эм... А большее число вариантов предполагается пару сотен лет перебирать? Проблема кода из #4 скорее в его тормознутости по сравнению с описанным Вами вариантом, но не в его ограниченности... ИМХО.
    r90
    Массив индексов пришлось бы использовать и для рекурсивного перебора, т.к. самый внутренний цикл должен знать все индексы, выбранные внешними циклами. Поэтому с тем же успехом и рекурсивный вариант тогда можно назвать "вариантом с массивом итераторов". Тем не менее на случай, если Вы увидите сходство со своим неописанным способом с массивом итераторов, начало второго предложения поста #4 содержит второе замечание, дающее мне на основе Вашей оценки "сложности" заблаговременный аргумент в пользу отличия способа.
    Тут Вы правы, конечно. Для простого последовательного инкрементирования (в системе счисления с переменным основанием) вариант с отображением — неудачный.
    На двух с половиной сойдёмся? :)
     
  9. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    l_inc
    Нет. Точнее если заниматься казуистикой, то пожалуй придётся назвать, но по логике -- это не так. Каждый из итераторов пробегающих массив, в случае рекурсии, будет создаваться на стеке при вызове функции, и удаляться оттуда при выходе из этой функции. Внутрь вложенного рекурсивного вызова будут передаваться лишь уже зафиксированные значения нескольких итераторов, которые не будут меняться в процессе работы этого рекурсивного вызова.
    Если же всё же заняться казуистикой, и поковыряться в логике рекурсивного алгоритма, то мы быстро придём к выводу, что рекурсивный алгоритм -- это не самостоятельный вариант, а небольшая модификация предложенного Вами варианта, и на выходе мы получим на два с половиной варианта, а полтора. ;)
    Хотя, при таком подходе, можно так же доказать, что и Ваш вариант с делениями и остатками -- это самостоятельный вариант.
    Да мне плевать на самом деле, сколько их. Тут весь вопрос в том, какого масштаба изменение нужно внести в код, чтобы изменился алгоритм. Это абсолютно неинтересный вопрос, и чтобы не участвовать в его обсуждении, я готов признать, что есть десять вариантов.
     
  10. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    r90
    Хех... вот так невинная шутка (намёк на базарный диалог) легко превращается в "неинтересный вопрос". Ладно, больше не оффтоплю.
     
  11. r90

    r90 New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2005
    Сообщения:
    898
    l_inc
    Ты предлагаешь заняться выяснением того, кто начал этот базарный диалог, а кто его спровоцировал?
    Не превращается, а так и есть. Если продолжать этот вопрос развивать, мы быстро скатимся к дискуссии о том, будет ли изменение имени переменной изменением алгоритма.
    Попытка уйти с высоко поднятой головой?
     
  12. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    r90
    O_O Утро неудачное что ли выдалось?
    Я предлагаю посмотреть Вам в толковом словаре смысл слова шутка.
    Вообще-то попытка согласиться, что выяснение числа способов не имеет смысла. Это во-первых.
    А во-вторых, с чего мне её опускать? Я хоть в чём-то был неправ?