Комбинация списка с заданной длиной, за которой следует перестановка в Прологе? - PullRequest
Новая
       11

Комбинация списка с заданной длиной, за которой следует перестановка в Прологе?

0 голосов
/ 07 декабря 2018

Мне нужен предикат для возврата списка со всеми комбинациями входного списка, а размер результата списка указан во втором параметре, предикат будет выглядеть следующим образом 

permutInListN( +inputList, +lengthListResult, -ListResult),

пример: 

permutInListN([1,2,3],2,L).
? L=[1,2].
? L=[2,1].
? L=[1,3].
? L=[3,1].
? L=[2,3].
? L=[3,2].

Комбинации [1,2,3] в списке L с длиной 2.без повторений, возможно, с использованием зачета.

это мой код, но он вообще не работает, нет генерации всех решений 

permutInListN(_, 0, []).
permutInListN([X|Xs], N, [X|Ys]) :- N1 is N-1, permutInListN(Xs,N1,Ys).
permutInListN([_|Xs], N, Y) :- N>0, permutInListN(Xs,N,Y).

?permutInListN([1,2,3],2,L).
L = [1, 2]
L = [1, 3]
L = [2, 3]

заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 07 декабря 2018

Перестановка результата

Ваш предикат permutInListN/3 в основном берет N элементов в упорядоченном порядке из заданного списка, но порядок выбранных элементов - этотакой же, как и в оригинальном порядке.

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

permutInListN(L, N, R) :-
    takeN(L, N, S),
    permutation(S, R).

с takeN/3, почти эквивалентнымпредикат, который вы определили: 

takeN(_, 0, []).
takeN([X|Xs], N, [X|Ys]) :-
    N > 0,
    N1 is N-1,
    takeN(Xs,N1,Ys).
takeN([_|Xs], N, Y) :-
    N > 0,
    takeN(Xs,N,Y).

permutation/3 [swi-doc] - это предикат из библиотеки lists [swi-doc] .

Использование N select/3 s

Мы также можем решить эту проблему N раз, используя select/3 предикат [swi-doc] .select(X, L, R) берет элемент X из списка, а R - список без этого элемента.Таким образом, мы можем рекурсивно пропустить список и каждый раз удалять элемент, пока не удалим N элементов, таких как: 

permutInListN(_, 0, []).
permutInListN(L, N, [X|T]) :-
    N > 0,
    N1 is N-1,
    select(X, L, R),
    permutInListN(R, N1, T).
0 голосов
/ 07 декабря 2018

Требуется комбинация, за которой следует перестановка.

Для комбинации: 

comb(0,_,[]).

comb(N,[X|T],[X|Comb]) :-
    N>0,
    N1 is N-1,
    comb(N1,T,Comb).

comb(N,[_|T],Comb) :-
    N>0,
    comb(N,T,Comb).

Пример: 

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

Для перестановки просто используйте SWI-Prologpermutation/2 в списках библиотек 

:- use_module(library(lists)).

?- permutation([1,2],R).
R = [1, 2] ;
R = [2, 1] ;
false.

Соединение их 

comb_perm(N,List,Result) :-
    comb(N,List,Comb),
    permutation(Comb,Result).

По вашему запросу 

?- comb_perm(2,[1,2,3],R).
R = [1, 2] ;
R = [2, 1] ;
R = [1, 3] ;
R = [3, 1] ;
R = [2, 3] ;
R = [3, 2] ;
false.

Изменено для вашего предиката 

permutInListN(List,N,Result) :-
    comb(N,List,Comb),
    permutation(Comb,Result).

Пример 

?- permutInListN([1,2,3],2,R).
R = [1, 2] ;
R = [2, 1] ;
R = [1, 3] ;
R = [3, 1] ;
R = [2, 3] ;
R = [3, 2] ;
false.
...