การรวมกันของหลายรายการ - อารัมภบท

คำตอบนี้ล่าเงินรางวัลที่เสนอ "สำหรับวิธีแก้ปัญหาที่แท้จริงซึ่งคำนึงถึง 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_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).

สิ่งนี้ควรใช้ได้กับ Prologs โดยไม่มีข้อจำกัด ด้วยข้อจำกัด จะต้องพิจารณา bagof/3 ใหม่ เนื่องจากข้อจำกัดในการคัดลอกเป็นภูมิประเทศที่มีการกำหนดไว้ไม่ดี

ต่อไปนี้เป็นวิธีดำเนินการโดยใช้ 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 ได้อย่างไร?

1. เราดูคำตอบของคำถามหลัง:

   ?- list_comb([[f,g],[x,y,z]], Ess0).
   Ess0 = [[f,x],[f,y],[f,z], [g,x],[g,y],[g,z]].

2. ... วาง 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]].

3. ... จากนั้นทำเช่นเดียวกันกับ 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]]].

4. หากต้องการรับจากรายการไปยังรายการให้ใช้ append/2

ฉันหวังว่าคำอธิบายนี้จะอธิบายได้ชัดเจนมากกว่าทำให้เกิดความสับสน :)

แนวทางของ @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.