, объединяющий элементы нескольких списков

Question

Я хочу взять произвольное количество списков и вернуть список комбинаций элементов, но только объединение одного элемента из каждого списка. Все, что у меня есть, это sudo-код, потому что я не знаю, с чего начать.

Я нашел решение этой программы в вопросе Combining the elements of 2 lists, но я не понимаю этого scala-кода. Я пишу свою программу в Tcl, но если вы можете помочь мне свободно писать свой ответ в любом виде, как java или python или псевдокод или что-то еще. Может ли кто-нибудь помочь мне привести следующий псевдо-код в жизнь?

, например:

# example: {a b} {c} {d e} 
    # returns: {a c d} {a c e} {b c d} {b c e} 
    # how? 
    # example: {a b} {c} {d e} 
    # iters: 0  0 0 
    #   0  0  1 
    #    1 0 0 
    #    1 0  1 
    # 
    # 
    # set done false 
    # 
    # while {!done} { 
    # 
    # list append combination_of_list due to iteration counts 
    # 
    # foreach list $lists { 
    #  increment the correct count (specifically {0->1} {0->0} {0->1}) } 
    #  reset the approapraite counts to 0 
    # } 
    # 
    # if all the counts in all the lists are at or above their max { 
    #  set done true 
    # } 
    # } 

Answer 1

Различные решения Tcl обсуждаются на этой странице: Cartesian product of a list of lists

Донал Fellows представляет этот вариант в конце страницы:

proc product args { 
    set xs {{}} 
    foreach ys $args { 
     set result {} 
     foreach x $xs { 
      foreach y $ys { 
       lappend result [list {*}$x $y] 
      } 
     } 
     set xs $result 
    } 
    return $xs 
} 

Выполнение этого типа дает вам результат:

% product {a b} {c} {d e} 
{a c d} {a c e} {b c d} {b c e} 

Документация: foreach, lappend, list, proc, return, set, {*} (syntax)

Answer 2

Вот псевдокод, описывающий алгоритм, который генерирует все комбинации:

list_of_lists = {{a b}{c}{d e}} 

def copy(list): 
    copy = {} 
    for element in list: 
     copy.add(element) 
    return copy; 
def combine(list1, list2): 
    combinations = {} 
    for item1 in list1: 
     for item2 in list2: 
      combination = copy(item1) 
      combination.add(item2) 
      combinations.add(combination) 
    return combinations 

results = {{}} 
while list_of_lists.length>0: 
    results = combine(results, list_of_lists[0]) 
    list_of_lists.remove(0) 

Она начинается путем объединения {{}} с {a b c} , который производит {{a} {b}}, который будет объединен с {c} для генерации {{a c} {b c}} на следующей итерации и т. Д.

Update: Javascript версия:

var list_of_lists = [["a", "b"],["c"],["d", "e"]]; 

function copy(list) { 
    var copy = []; 
    for (element of list) { 
     copy.push(element); 
    } 
    return copy; 
} 

function combine(list1, list2) { 
    var combinations = []; 
    for (let item1 of list1) { 
     var combination = copy(item1); 
     for (let item2 of list2){ 
      combination.push(item2); 
      combinations.push(combination); 
     } 

    } 
    return combinations; 
} 

results = [[]] 
while (list_of_lists.length>0) { 
    results = combine(results, list_of_lists[0]); 
    list_of_lists.splice(0,1); 
} 
console.log(results);