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의 정수 제약 조건을 사용하여 목록의 크기를 제한하는 방법을 알지 못해서 실망했습니다.

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

당신을 준다 : 당신은 당신이 할 수있는 모든 해답을 열거하려면, 당신과 함께 회원의 원래 구현 http://swish.swi-prolog.org/p/allcombos.pl

Answer 1

: 여기

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

는 SWISH에 모든 관련 코드 답변 :

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가이 경우에 당신을 도울 수 있다고 생각하지 않습니다.

편집

내가 제목에 명시 적으로 CLPFD에 대해 물어 것을 알 수있다.코드가 작동하지 않는 이유는 코드를 실제로 열거하지 않기 때문입니다.

L in 0..Bound 

다음 술어의 경우, L은 아직 바인드 해제되어 있으며 제한 조건을 가지고 있습니다. 그래서 membersWithLength는 새로운 길이의 반복을 계속 반복 할 것이고, 인스턴스화 된 길이라면 제약 조건이 실패하고 다시 시도하는 것을 볼 것입니다. 다음 예에서 확인할 수 있습니다.

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

루프가 길이 때문에 계속 표시됩니다. 이를 제한하려면 L을 호출하기 전에 L을 인스턴스화해야합니다. 레이블을 사용할 수 있습니다. 이 다음 예제는 루프를 수행하지 않습니다.

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