Мне нужно найти комбинации в списке списков. Например, приведите следующий список,
List = [[1, 2], [1, 2, 3]]
Это должен быть результат,
Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]]
Другой пример:
List = [[1,2],[1,2],[1,2,3]]
Comb = [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3]....etc]
Я знаю, как это сделать для списка с двумя подсписками, но он должен работать для любого количества подсписок.
Я новичок в Prolog, помогите, пожалуйста.
Этот ответ охотится за предлагаемой наградой «за чистое решение, которое также учитывает Ess». Здесь мы обобщаем предыдущий ответ следующим образом:
list_crossproduct(Xs, []) :-
member([], Xs).
list_crossproduct(Xs, Ess) :-
Ess = [E0|_],
same_length(E0, Xs),
maplist(maybelonger_than(Ess), Xs),
list_comb(Xs, Ess).
maybelonger_than(Xs, Ys) :-
maybeshorter_than(Ys, Xs).
maybeshorter_than([], _).
maybeshorter_than([_|Xs], [_|Ys]) :-
maybeshorter_than(Xs, Ys).
list_crossproduct/2 становится двунаправленным, поскольку раньше связывает Xs и Ess.
?- list_comb(Xs, [[1,2,3],[1,2,4],[1,2,5]]). nontermination % BAD! ?- list_crossproduct(Xs, [[1,2,3],[1,2,4],[1,2,5]]). Xs = [[1],[2],[3,4,5]] % this now works, too ; false.
Пример запроса с несколькими ответами:
?- list_crossproduct(Xs, [[1,2,3],[1,2,4],[1,2,5],X,Y,Z]).
X = [1,2,_A],
Y = [1,2,_B],
Z = [1,2,_C], Xs = [[1],[2],[3,4,5,_A,_B,_C]]
; X = [1,_A,3],
Y = [1,_A,4],
Z = [1,_A,5], Xs = [[1],[2,_A],[3,4,5]]
; X = [_A,2,3],
Y = [_A,2,4],
Z = [_A,2,5], Xs = [[1,_A],[2],[3,4,5]]
; false.
nilmemberd(Xs) вместо member([],Xs).
- person repeat; 26.03.2020
Для полноты, вот расширенная версия моей версии комментария. Обратите внимание на nilmemberd_t/2, который вдохновлен memberd_t/2.
nilmemberd_t([], false).
nilmemberd_t([X|Xs], T) :-
if_(nil_t(X), T = true, nilmemberd_t(Xs, T)).
nil_t([], true).
nil_t([_|_], false).
list_comb(List, []) :-
nilmemberd_t(List, true).
list_comb(List, Ess) :-
bagof(Es, maplist(member,Es,List), Ess).
Вышеупомянутая версия показывает, что в моем ответе на комментарий отсутствовало "только" первое предложение. Может быть, даже короче:
nilmemberd([[]|_]).
nilmemberd([[_|_]|Nils]) :-
nilmemberd(Nils).
Это должно работать для Прологов без ограничений. С ограничениями, bagof / 3 придется пересмотреть, поскольку копирование ограничений - это плохо определенная местность.
findall вместо bagof, чтобы избежать ошибки findall( Es, maplist( member,Es, [[1,2],t,[1]]), Ess). с [] вместо неудачи. но ваша версия также ошибочно преуспевает с [] для [[1,2],[],t,[1]].
- person Will Ness; 23.03.2020
bagof неправильно терпит неудачу на [[1,1],[],[1]], но правильно findall (в данном случае) преуспевает с [].
- person Will Ness; 23.03.2020
bagof/3 правильно обрабатывает переменные, тогда как findall/3 копирует их как сумасшедший
- person false; 23.03.2020
list_comb(T,[[1]]). цикл представляет собой гораздо меньшую проблему, чем когда он завершился бы неудачей, поскольку цикл не может быть интерпретирован как истинный или ложный. И для list_comb([[1,2],[],t,[1]],X).: если вы видите это обобщение как проблему, почему тогда вы также выбираете успех для list_comb([[1|non_list]],X)? Мне это кажется приемлемым, но если вы настаиваете, добавьте maplist(maplist(\_^true), List) в конце обоих правил.
- person false; 24.03.2020
list_comb( [[1 | t]], X ). со своим кодом, и он не работает должным образом.
- person Will Ness; 26.03.2020
Вот способ сделать это с помощью maplist/3 и append/2:
list_comb([], [[]]). list_comb([Xs|Xss], Ess) :- Xs = [_|_], list_comb(Xss, Ess0), maplist(aux_x_comb(Ess0), Xs, Esss1), append(Esss1, Ess). aux_x_comb(Ess0, X, Ess1) :- maplist(head_tail_list(X), Ess0, Ess1). head_tail_list(X, Xs, [X|Xs]).
Пример запроса:
?- list_comb([[a,b],[f,g],[x,y,z]], Ess).
Ess = [[a,f,x],[a,f,y],[a,f,z],
[a,g,x],[a,g,y],[a,g,z],
[b,f,x],[b,f,y],[b,f,z],
[b,g,x],[b,g,y],[b,g,z]].
Вот как это работает! В качестве примера рассмотрим эти цели:
list_comb([[a,b],[f,g],[x,y,z]], Ess)
list_comb([ [f,g],[x,y,z]], Ess0)
Как мы можем перейти от Ess0 к Ess?
Смотрим ответы на последний вопрос:
?- list_comb([[f,g],[x,y,z]], Ess0). Ess0 = [[f,x],[f,y],[f,z], [g,x],[g,y],[g,z]].
... поместите a перед [f,x], ..., [g,z] ...
?- maplist(head_tail_list(a),
[[f,x],[f,y],[f,z],
[g,x],[g,y],[g,z]], X).
X = [[a,f,x],[a,f,y],[a,f,z],
[a,g,x],[a,g,y],[a,g,z]].... затем сделайте то же самое для b.
maplist(aux_x_comb) помогает нам обрабатывать все вопросы:
?- maplist(aux_x_comb([[f,x],[f,y],[f,z],
[g,x],[g,y],[g,z]]),
[a,b], X).
X = [[[a,f,x],[a,f,y],[a,f,z],
[a,g,x],[a,g,y],[a,g,z]],
[[b,f,x],[b,f,y],[b,f,z],
[b,g,x],[b,g,y],[b,g,z]]].Чтобы перейти из списка списков в список, используйте append/2.
Надеюсь, это объяснение было больше ускользающим, чем сбивающим с толку :)
Ess не влияет на завершение - по крайней мере, в некоторых случаях
- person false; 17.03.2020
Изюминка подхода @ false:
%list_comb( ++LL, -Ess)
list_comb( LL, Ess):-
is_list( LL),
maplist( is_list, LL),
findall( Es, maplist( member, Es, LL), Ess).
Тестирование:
41 ?- list_comb( [[1,2],[1],[1]], X). X = [[1, 1, 1], [2, 1, 1]]. 42 ?- list_comb( [[1,2],[1],[1,2,3]], X). X = [[1, 1, 1], [1, 1, 2], [1, 1, 3], [2, 1, 1], [2, 1, 2], [2, 1, 3]]. 43 ?- list_comb( [[1,2],[],[1,2,3]], X). X = []. 44 ?- list_comb( [[1,2],t,[1,2,3]], X). false. 45 ?- list_comb( t, X). false.
