Перестановочные комбинации элементов списка - Пролог

Question

Как я могу сгенерировать все возможные комбинации элементов списка?

Например, учитывая список [1,2,3], я хочу создать предикат с формой comb([1,2,3], L)., который должен вернуть следующий ответ для L:

[1]  
[2]  
[3]  
[1,2]  
[2,1]  
[1,3]  
[3,1]  
[2,3] 
[3,2]  
[1,2,3]  
[1,3,2]  
[2,1,3]  
[2,3,1]  
[3,1,2]  
[3,2,1] 

Answer 1

То, что вы запрашиваете, включает в себя как комбинации (выбор подмножества), так и перестановки (перераспределение порядка) списка.

Ваш пример вывода подразумевает, что пустой список не считается допустимым решением, поэтомубудет исключать его в последующей реализации.Пересмотрите, был ли это недосмотр.Кроме того, эта реализация создает решения в другом порядке, чем в вашем примере.

comb(InList,Out) :-
    splitSet(InList,_,SubList),
    SubList = [_|_],     /* disallow empty list */
    permute(SubList,Out).

splitSet([ ],[ ],[ ]).
splitSet([H|T],[H|L],R) :-
    splitSet(T,L,R).
splitSet([H|T],L,[H|R]) :-
    splitSet(T,L,R).

permute([ ],[ ]) :- !.
permute(L,[X|R]) :-
    omit(X,L,M),
    permute(M,R).

omit(H,[H|T],T).
omit(X,[H|L],[H|R]) :-
    omit(X,L,R).

Протестировано с Amzi!Пролог:

?- comb([1,2,3],L).

L = [3] ;

L = [2] ;

L = [2, 3] ;

L = [3, 2] ;

L = [1] ;

L = [1, 3] ;

L = [3, 1] ;

L = [1, 2] ;

L = [2, 1] ;

L = [1, 2, 3] ;

L = [1, 3, 2] ;

L = [2, 1, 3] ;

L = [2, 3, 1] ;

L = [3, 1, 2] ;

L = [3, 2, 1] ;
no

Answer 2

Сохраняйте чистоту, определяя comb/2 на основе same_length/2, prefix/2, foldl/4 и select/3:

comb(As,Bs) :-
   same_length(As,Full),
   Bs = [_|_],
   prefix(Bs,Full),
   foldl(select,Bs,As,_).

Вот пример запроса, заданного OP:

?- comb([1,2,3],Xs).
  Xs = [1]
; Xs = [2]
; Xs = [3]
; Xs = [1,2]
; Xs = [1,3]
; Xs = [2,1]
; Xs = [2,3]
; Xs = [3,1]
; Xs = [3,2]
; Xs = [1,2,3]
; Xs = [1,3,2]
; Xs = [2,1,3]
; Xs = [2,3,1]
; Xs = [3,1,2]
; Xs = [3,2,1]
; false.

Хорошо!Но что, если список, указанный в качестве первого аргумента, содержит дубликаты?

?- comb([1,1,2],Xs).
  Xs = [1]
; Xs = [1]                   % (redundant)
; Xs = [2]
; Xs = [1,1]
; Xs = [1,2]
; Xs = [1,1]                 % (redundant)
; Xs = [1,2]                 % (redundant)
; Xs = [2,1]
; Xs = [2,1]                 % (redundant)
; Xs = [1,1,2]
; Xs = [1,2,1]
; Xs = [1,1,2]               % (redundant)
; Xs = [1,2,1]               % (redundant)
; Xs = [2,1,1]
; Xs = [2,1,1]               % (redundant)
; false.

Не совсем! Можем ли мы избавиться от лишних ответов?Да, просто используйте selectd/3!

comb(As,Bs) :-
   same_length(As,Full),
   Bs = [_|_],
   prefix(Bs,Full),
   foldl(selectd,Bs,As,_).

Так что давайте снова запустим запрос выше с улучшенной реализацией comb/2!

?- comb([1,1,2],Xs).
  Xs = [1]
; Xs = [2]
; Xs = [1,1]
; Xs = [1,2]
; Xs = [2,1]
; Xs = [1,1,2]
; Xs = [1,2,1]
; Xs = [2,1,1]
; false.

Answer 3

существует предопределенный предикат, называемый перестановкой ...

1 ?- permutation([1,2,3],L).
L = [1, 2, 3] ;
L = [2, 1, 3] ;
L = [2, 3, 1] ;
L = [1, 3, 2] ;
L = [3, 1, 2] ;
L = [3, 2, 1] .

2 ?- listing(permutation).
lists:permutation([], [], []).
lists:permutation([C|A], D, [_|B]) :-
        permutation(A, E, B),
        select(C, D, E).

lists:permutation(A, B) :-
        permutation(A, B, B).

true.

надеюсь, это поможет ..

Answer 4

Подсказка: это легко сделать, если вы написали предикат inselt(X,Y,Z), который действует, если любая вставка Y в X дает Z:

inselt([E|X], Y, [E|Z]) :- inselt(X,Y,Z).
inselt(X, Y, [Y|X]).

Тогда comb/3 может быть рекурсивно закодирован с использованием inselt/3.