Как связать все комбинации пролога с clp (fd)?

Question

То, что я хотел сделать, это сгенерировать все комбинации элементов из данного списка. Например: Из [a, b, c], я могу:

[] 
[a] 
[b] 
[c] 
[a,a] 
[a,b] 
[a,c] 
[b,a] 
... 

И так далее. Возможно, есть волшебный пролог с одним слоем, который делает это. Если так, я хотел бы это услышать.

Однако мой вопрос не в том, чтобы решить эту конкретную проблему и в большей части запроса, чтобы кто-то объяснил мне некоторые тонкости алгоритма поиска Prolog.

Так вот пока что я сделал первый решить вышеуказанную проблему:

members([], _). 
members([X|Xs], List) :- 
    member(X,List), 
    members(Xs, List). 

Это прекрасно работает, но возвращает все возможные результаты, а не в большом порядке:

[] 
[a] 
[a,a] 
[a,a,a] 

Хорошо, что нет проблема. Я просто хочу, чтобы все комбинации были до определенной длины. Поэтому я решил сначала получить те, которые имеют точно определенную длину:

membersWithLength(Members, List, Bound) :- 
    L = Bound, 
    length(Members, L), members(Members, List). 

Это прекрасно работает, например. для длины 2:

[a,a] 
[a,b] 
[a,c] 
... 

И так далее. Теперь моя попытка использовать clpfd использовать описанную выше функцию, чтобы получить все списки до определенной длины пошло наперекосяк:

:- use_module(library(clpfd)). 


membersLessThan(Members, List, Bound) :- 
    L in 0..Bound, % I also tried L #=< Bound 
    membersWithLength(Members, List, L). 

Вид работ. Находит правильные результаты (списки с длиной меньше, чем Bound). Но после того, как он находит их, он непрерывно ищет больше результатов. Например. для длины 2:

[] 
[a] 
[b] 
[c] 
[a,a] 
[a,b] 
... 
[c,c] 
Hangs looking for more solutions. 

Я думаю, что это сердце моего вопроса. Может кто-нибудь объяснить, почему (по следам) пролог продолжает проверять более крупные и большие списки как возможные решения, даже если они все обречены на провал? И может ли кто-нибудь сказать мне, есть ли способ помочь прологу избежать этого обреченного пути?

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

membersLessThan_(Members, List, Bound) :- 
    numlist(0,Bound,ZeroToBound), 
    member(L, ZeroToBound), 
    membersWithLength(Members, List, L). 

Здесь все соответствующий код на SWISH: http://swish.swi-prolog.org/p/allcombos.pl

Answer 1

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

length(L, _), members(L, [a,b,c]). 

, который дает вам ответы:

L = [] ; 
L = [a] ; 
L = [b] ; 
L = [c] ; 
L = [a, a] ; 
L = [a, b] ; 
L = [a, c] ; 
L = [b, a] ; 
L = [b, b] ; 
L = [b, c] ; 
L = [c, a] ; 
L = [c, b] ; 
L = [c, c] ; 
L = [a, a, a] ; 
L = [a, a, b] ; 
L = [a, a, c] ; 
L = [a, b, a] 

Это распространенная идиома для itera которое позволяет вам правильно отображать все ответы. Я не думаю, что clpfd может помочь вам в этом случае.

EDIT

Я вижу, что в названии явно спросить о CLPFD.Причина, по которой ваш код не работает, заключается в том, что когда вы делаете

L in 0..Bound 

Вы на самом деле не перечисляете эти значения. Для следующих предикатов L все еще несвязано и имеет ограничение. Таким образом, членыWithLength будут продолжать цикл, повторяя новые длины, и после того, как он будет создан, он увидит, что ограничение завершилось с ошибкой и повторите попытку. Вы можете увидеть это в этих примерах:

L in 0..2, length(X, L) 

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

L in 0..2, label([L]), length(X, L)