Генерирующие цепи от порядка списков

Question

Я ищу, как выполнить то, что я несколько хватку, но не:

У меня есть п число списков разного размера:

{A, B, C, D} 
    {1,2} 
     {X, Y, Z} 
      ...to the nth potentially 

Как я могу генерировать все возможные цепочки из 1 предмета с каждого уровня A1X, A1Y, A1Z и т. Д. Его альготритмическая и математическая задача, без ее домашней работы (я знаю, что школа начинается), ее часть того, над чем я работаю , У меня нет кода. Мне просто нужно указать в правильном направлении, чтобы сформулировать мои условия.

Answer 1

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

Фактически вы говорите об образовании списков Cartesian Product. Это можно сделать по-разному. Если количество списков неизвестно заранее, рекурсивный подход является наиболее естественным.

Пусть L1*L2* ... *Ln обозначим список всех строк, которые имеют форму s1+s2+...+sn где si в Li и + является оператором конкатенации. Для основы вы можете либо взять n ==1, либо один список, либо n == 0, ни один список. Во многих отношениях последний более изящный, и в этом случае естественно определить произведение пустого списка строк как список, единственным элементом которого является пустая строка.

Тогда:

Вернуться [''] если n == 0

В противном случае вернуть

[a+b | a ranges over L1 and b ranges over (L2 * L3 * ... * Ln)] 

где (L2 * L3 * ... *Ln) был alread вычисляется рекурсивно (который будет просто пустая строка, если п 1).

Последний список можно легко создать в вложенном цикле или выразить непосредственно на любом языке, который поддерживает list comprehensions.

Вот реализация Python, который возвращает список всех продуктов дан список списков строк (сокращенно lls в коде):

def product(lls): 
    if len(lls) == 0: 
     return [''] 
    else: 
     return [a+b for a in lls[0] for b in product(lls[1:])] 

Испытано как таким образом:

lists_of_strings = [['A','B','C','D'],['1','2','3'],['X','Y','Z']] 
print(product(lists_of_strings)) 

С выходом:

['A1X', 'A1Y', 'A1Z', 'A2X', 'A2Y', 'A2Z', 'A3X', 'A3Y', 'A3Z', 'B1X', 'B1Y', 'B1Z', 'B2X', 'B2Y', 'B2Z', 'B3X', 'B3Y', 'B3Z', 'C1X', 'C1Y', 'C1Z', 'C2X', 'C2Y', 'C2Z', 'C3X', 'C3Y', 'C3Z', 'D1X', 'D1Y', 'D1Z', 'D2X', 'D2Y', 'D2Z', 'D3X', 'D3Y', 'D3Z'] 

В самом Python не так много мотивов ция, чтобы сделать это, так как itertools модуль имеет хороший продукт и тот же продукт может быть выражен как:

[''.join(p) for p in itertools.product(*lists_of_strings)]