Создайте список, выбрав 1 элемент из каждого списка (пролог)

Question

У меня есть список, который содержит списки.Я хочу создать список перестановок.

Пример:

generate_perm([[3],[1,2,3,4],[1,2]], P).
P = [[3,1,1], [3,2,1], [3,3,1], [3,4,1], [3,1,2], [3,2,2], [3,3,2], [3,4,2]];
no

Таким образом, выходные списки: n-й элемент является элементом n-го списка из входных списков.То, что я уже пробовал: использовать член, и найти все, но я застрял.Так как я новичок в прологе, я всегда думаю императивно.

Мой код пока дает 1 решение:

generate_perm([],_).
generate_perm([H|Tl], Perm):- member(M, H), append(Perm, [M], Perm2),
                              generate_perm(Tl, Perm2).

Отладка этого:

| ?- generate_perm([[3],[1,2,3,4],[1,2]], P).
 #      1      1 Call: member(_4961,[3]) ? 
 #      1      1 Exit: member(3,[3]) ? 
 #      2      1 Call: generate_perm([[1,2,3,4],[1,2]],[3]) ? 
 #      3      2 Call: member(_56173,[1,2,3,4]) ? 
?#      3      2 Exit: member(1,[1,2,3,4]) ? 
 #      4      2 Call: generate_perm([[1,2]],[3,1]) ? 
 #      5      3 Call: member(_138349,[1,2]) ? 
?#      5      3 Exit: member(1,[1,2]) ? 
 #      6      3 Call: generate_perm([],[3,1,1]) ? 
 #      6      3 Exit: generate_perm([],[3,1,1]) ? 
?#      4      2 Exit: generate_perm([[1,2]],[3,1]) ? 
?#      2      1 Exit: generate_perm([[1,2,3,4],[1,2]],[3]) ? 
P = [] ? 

Итакответ есть (Call: generate_perm ([], [3,1,1]), здесь ответ [3,1,1]), но он дает мне пустой список, и я не могу понять, почему,И еще один шаг, где мне нужна помощь, я не знаю, как получить все решения в 1 списке.

Answer 1

Как сказано, «императивное мышление» обычно не очень хорошо с Прологом.Вы должны думать в терминах (рекурсивных) определений.

Например, мы можем сказать, что crossprod/2, где первый список пуст, дает одно решение: пустой список, поэтому мы можем указать это как:

crossprod([], []).

теперь нам все еще нужно придумать индуктивный случай: если мы можем сгенерировать перестановку для списка n-1 элементов, то как мы должны сгенерировать перестановку для спискаиз n элементов (с n≥0 ).

Для таких списков у нас есть первый элемент («голова»), здесь head - это список (так как первый аргумент должен быть списком списков).Таким образом, мы можем использовать member/2, чтобы взять элемент из списка sub , этот элемент будет head (первый элемент) списка результатов, затем мы передаем хвост (оставшиесяsublists) рекурсивно к crossprod/2 для генерации хвоста результата, например:

crossprod([H|T], [X|R]) :-
    member(X, H),
    crossprod(T, R).

или полностью, это дает:

crossprod([], []).
crossprod([H|T], [X|R]) :-
    member(X, H),
    crossprod(T, R).

Так что теперь мы можем генерировать элементы из«перекрестное произведение» данного списка «наборов», например:

?- crossprod([[3],[1,2,3,4],[1,2]], P).
P = [3, 1, 1] ;
P = [3, 1, 2] ;
P = [3, 2, 1] ;
P = [3, 2, 2] ;
P = [3, 3, 1] ;
P = [3, 3, 2] ;
P = [3, 4, 1] ;
P = [3, 4, 2].

Если мы затем хотим создать список из них (что довольно странно, обычно лучше генерировать ответы независимо), мы можем использовать findall/3:

generate_perm (S, R): - findall (Ri, crossprod (S, Ri), R).

и затем мы получим список кросс-продукты, такие как:

?- generate_perm([[3],[1,2,3,4],[1,2]], P).
P = [[3, 1, 1], [3, 1, 2], [3, 2, 1], [3, 2, 2], [3, 3, 1], [3, 3, 2], [3, 4|...], [3|...]].