Пусть имеется k списков произвольного типа с различным количеством элементов. Напр.: x1=["one","two","three"] x2=[1,2,3,4,5] x3=[234,543,12555,521,22] ... Нужнен алгоритм перебора значений всех этих списков и составления комбинаций из этих значений Пр.: ["one",1,234] ["one",2,234] ... Пните меня, пожалуйста, в сторону матчасти, позволяющей реализовать данную задачу эффективно
cryptic_elk делаеш "к" количество вложенных циклов, с количеством итераций - равных размеру каждого списка, а в центральном цикле составляешь результат из данных списков из элементов с индексами циклов. как-то так ..
wsd А если k вводится с клавиатуры? Тут есть два варианта. Либо рекурсия, либо массив итераторов (индексов) по массивам. Рекурсия проще. Функция выполняет цикл перебирая элементы одного массива, и на каждой итерации цикла вызывает сама себя передавая в качестве, чуть меньше массивов (на один меньше), и начало текущей комбинации. Массив же индексов... Там тоже в общем ничего сложного нет, но лень объяснять.
На случай, если кто-то вдруг решил, что варианта всего два. Уж не знаю, проще ли рекурсия, а обойтись можно ровно одним циклом, перебирающим натуральные числа, и отображением натурального числа на комбинацию. Отображение может выглядеть таким образом: Код (Text): //num — (на входе) число, которое хотим отобразить //combination — (на выходе) массив, представляющий собой комбинацию (индексов в списках) //listLen — (на входе) массив, содержащий размеры списков //listCount — (на входе) длина массива listLen и соответственно массива combination void FillCombination(DWORD num, DWORD *combination, DWORD *listLen, DWORD listCount) { DWORD prod = 1; for (DWORD i = 0; i < listCount; i++) prod *= listLen[i]; for (DWORD i = 0; i < listCount; i++) prod /= listLen[i], combination[i] = num/prod, num %= prod; } Тогда перебрать комбинации можно одним простым циклом: Код (Text): const int LIST_SIZE = 3; DWORD listLen[LIST_SIZE] = {3,37,5}, combination[LIST_SIZE]; for (DWORD i = 0; i < 3*37*5; i++) { //получаем комбинацию FillCombination(i, combination, listLen, LIST_SIZE); //Выводим комбинацию for (DWORD j = 0; j < LIST_SIZE; j++) printf("%2d ", combination[j]); printf("\n"); } Разумеется, глупо каждый раз внутри FillCombination вычислять prod. В данном случае это сделано для наглядности.
Если по-русски, то у тебя есть трёхзначное число, где первая цифра - из интервала х1, вторая - из х2, третья - из х3. В общем случае стоило бы соорудить массив из трёх элементов, каждый из которого представляет разряд числа, и делать инкремент этого числа, после этого проверяя переполнение в каждом разряде и при необходимости выполняя перенос. Как только возникнет перенос в 3 разряде - процесс прекратить. Для списков с суммарным числом вариантов меньше 2^32 (или 2^64 с небольшими модификациями) можно использовать код l_inc.
l_inc Это вариант с массивом итераторов. Который CyberManiac описал чуть более подробно. У тебя в качестве массива итераторов выступает массив combination. Единственное что, я бы не стал заниматься маппингом int'а в вектор итераторов. Все эти деления и остатки от деления лишь ужасно тормозят код. Быстрее и проще будет впрямую "инкрементировать" вектор итераторов. Так что, доказательство того, что вариантов больше двух не зачитывается.
CyberManiac Эм... А большее число вариантов предполагается пару сотен лет перебирать? Проблема кода из #4 скорее в его тормознутости по сравнению с описанным Вами вариантом, но не в его ограниченности... ИМХО. r90 Массив индексов пришлось бы использовать и для рекурсивного перебора, т.к. самый внутренний цикл должен знать все индексы, выбранные внешними циклами. Поэтому с тем же успехом и рекурсивный вариант тогда можно назвать "вариантом с массивом итераторов". Тем не менее на случай, если Вы увидите сходство со своим неописанным способом с массивом итераторов, начало второго предложения поста #4 содержит второе замечание, дающее мне на основе Вашей оценки "сложности" заблаговременный аргумент в пользу отличия способа. Тут Вы правы, конечно. Для простого последовательного инкрементирования (в системе счисления с переменным основанием) вариант с отображением — неудачный. На двух с половиной сойдёмся?
l_inc Нет. Точнее если заниматься казуистикой, то пожалуй придётся назвать, но по логике -- это не так. Каждый из итераторов пробегающих массив, в случае рекурсии, будет создаваться на стеке при вызове функции, и удаляться оттуда при выходе из этой функции. Внутрь вложенного рекурсивного вызова будут передаваться лишь уже зафиксированные значения нескольких итераторов, которые не будут меняться в процессе работы этого рекурсивного вызова. Если же всё же заняться казуистикой, и поковыряться в логике рекурсивного алгоритма, то мы быстро придём к выводу, что рекурсивный алгоритм -- это не самостоятельный вариант, а небольшая модификация предложенного Вами варианта, и на выходе мы получим на два с половиной варианта, а полтора. Хотя, при таком подходе, можно так же доказать, что и Ваш вариант с делениями и остатками -- это самостоятельный вариант. Да мне плевать на самом деле, сколько их. Тут весь вопрос в том, какого масштаба изменение нужно внести в код, чтобы изменился алгоритм. Это абсолютно неинтересный вопрос, и чтобы не участвовать в его обсуждении, я готов признать, что есть десять вариантов.
r90 Хех... вот так невинная шутка (намёк на базарный диалог) легко превращается в "неинтересный вопрос". Ладно, больше не оффтоплю.
l_inc Ты предлагаешь заняться выяснением того, кто начал этот базарный диалог, а кто его спровоцировал? Не превращается, а так и есть. Если продолжать этот вопрос развивать, мы быстро скатимся к дискуссии о том, будет ли изменение имени переменной изменением алгоритма. Попытка уйти с высоко поднятой головой?
r90 O_O Утро неудачное что ли выдалось? Я предлагаю посмотреть Вам в толковом словаре смысл слова шутка. Вообще-то попытка согласиться, что выяснение числа способов не имеет смысла. Это во-первых. А во-вторых, с чего мне её опускать? Я хоть в чём-то был неправ?
