создать список из списка списков

Question

Мне нужно сделать следующее: учитывая список списков, мне нужно найти все возможные комбинации списков, чтобы, если некоторые из этих списков принадлежат в такой комбинации, то у них нет общие элементы, а список, созданный путем добавления списков в комбинацию, имеет заданную длину. Есть идеи?

Пример:

Say P= [[1,2,3],[4,5,6],[2,5],[7,9],[7,10],[8],[10]]. 

N заданное число, скажем, N = 10. Мне нужно выполнить поиск через P, чтобы найти соответствующие списки без общих элементов и добавить их в список L, чтобы длина объединения L составляла 10. Таким образом, в приведенном выше примере:

L=[[1,2,3],[4,5,6],[7,9],[8],[10]]. Это может быть очень легко, но я новичок в Prolog

Answer 1

Учитывая, что никто не ответил, и прошло довольно много времени с тех пор, как я написал что-нибудь в Прологе, и я подумал, что мне нужна практика, вот как вы это сделаете.

Прежде всего, чтобы упростить создание комбинаций, мы создаем термин для предварительной обработки списков, чтобы соединить их с их длиной, чтобы избежать необходимости иметь длину несколько раз. Разрез позволяет избежать ненужных откатов:

with_lengths([], []) :- !. 
with_lengths([H|T1], [(Len, H)|T2]) :- 
    length(H, Len), 
    with_lengths(T1, T2). 

Вот comb/3 предиката, который используется для создания комбинаций:

comb(L, R, Max) :- 
    with_lengths(L, L1), 
    comb1(L1, R, Max). 

comb1/3 делает фактическую работу. Комментарии объясняют, что происходит:

% Combination works. 
comb1([], [], 0). 
% Try combining the current element with the remainder. 
comb1([(Len, Elem)|T1], [Elem|T2], Max) :- 
    NewMax is Max - Len, 
    comb1(T1, T2, NewMax). 
% Alternatively, ignore the current element and try 
% combinations with the remainder. 
comb1([_|T1], T2, Max) :- 
    comb1(T1, T2, Max).