Jika saya memiliki dua predikat yang menghasilkan nilai secara berurutan, misalnya:

between(1, 3, X), sub_atom(abc, _, 1, _, Y)

Bagaimana saya bisa mengulanginya sehingga saya mendapatkan solusi:

X = 1, Y = a ;
X = 2, Y = b ;
X = 3, Y = c.

Mencoba cara biasa tentu saja tidak berhasil:

?- between(1, 3, X), sub_atom(abc, _, 1, _, Y).
X = 1, Y = a ;
X = 1, Y = b ;
X = 1, Y = c ;
X = 2, Y = a ;

Tentu saja saya dapat mengumpulkan keduanya dalam daftar secara terpisah:

?- findall(X, between(1, 3, X), Xs), findall(Y, sub_atom(abc, _, 1, _, Y), Ys).
Xs = [1, 2, 3],
Ys = [a, b, c].

Tapi ini yang ingin saya hindari. Saya tidak ingin membuat daftar lengkapnya, mungkin terlalu besar. Atau mungkin saya ingin menggunakan sesuatu seperti between(1, inf, X) sebagai salah satu generator.


Tampaknya ada solusi untuk sesuatu yang serupa yang disebut merge dan diuraikan di sini: https://www.swi-prolog.org/pldoc/man?section=engine-examples tetapi melakukan sesuatu yang berbeda.

1
TA_intern 11 Mei 2021, 15:28

2 jawaban

Jawaban Terbaik

Saya pikir adalah mungkin untuk secara bersamaan mengunjungi solusi untuk dua predikat yang dapat dilacak kembali menggunakan mesin.

simultaneously_visit_generators(G1, G2, X-Y) :-
   engine_create(X, G1, E1),
   engine_create(Y, G2, E2),
   simultaneously_visit_engines(E1, E2, X-Y).

simultaneously_visit_engines(E1, E2, X-Y) :-
   (   engine_next(E1, X),
       engine_next(E2, Y)
   ->  true
   ;   !,
       fail ).

simultaneously_visit_engines(E1, E2, X-Y) :-
   simultaneously_visit_engines(E1, E2, X-Y).

Berikut beberapa contohnya:

?- simultaneously_visit_generators(between(1,3,X), sub_atom(abc,_,1,_,Y), X-Y).
X = 1,
Y = a ;
X = 2,
Y = b ;
X = 3,
Y = c ;
false.

?- simultaneously_visit_generators(between(1,inf,X), member(Y,[a,b,c]), X-Y).
X = 1,
Y = a ;
X = 2,
Y = b ;
X = 3,
Y = c ;
false.

?- simultaneously_visit_generators(between(1,2,X), between(1,inf,Y), X-Y).
X = Y, Y = 1 ;
X = Y, Y = 2 ;
false.

KOMPLEKSITAS WAKTU

Untuk melihat bahwa kompleksitas waktu adalah O(n), pertimbangkan predikat berikut:

running_time :-
   forall( between(16, 20, Exponent),
           ( N is 2**Exponent,
             time(findall(X-Y,
                          simultaneously_visit_generators(between(1, inf, X),
                                                          between(1, N, Y), X-Y), _L)))).

Hasil empiris (SWI-Prolog, versi 8.2.4):

?- running_time.
% 262,162 inferences, 0.063 CPU in 0.078 seconds (80% CPU, 4194592 Lips)
% 524,306 inferences, 0.125 CPU in 0.125 seconds (100% CPU, 4194448 Lips)
% 1,048,594 inferences, 0.297 CPU in 0.297 seconds (100% CPU, 3532106 Lips)
% 2,097,170 inferences, 0.531 CPU in 0.547 seconds (97% CPU, 3947614 Lips)
% 4,194,322 inferences, 1.094 CPU in 1.109 seconds (99% CPU, 3834809 Lips)
true.

Seperti yang dapat kita amati, ketika jumlah jawaban berlipat ganda, waktu juga berlipat ganda.

2
slago 12 Mei 2021, 05:14

Jawaban dari @slago adalah solusi untuk SWI-Prolog. Sekarang saya telah mendefinisikan predikat berikut:

:- meta_predicate zip(?,0, ?,0, -, -).

zip(T1, G1, T2, G2, A1, A2) :-
    engine_create(T1, G1, E1),
    engine_create(T2, G2, E2),
    repeat,
        (   engine_next(E1, A1),
            engine_next(E2, A2)
        ->  true
        ;   !, fail
        ).

Ini berfungsi sebagai jawaban lain:

?- zip(X, between(1, inf, X), Y, sub_atom(abc, _, 1, _, Y), A, B).
A = 1,
B = a ;
A = 2,
B = b ;
A = 3,
B = c ;
false.
1
TA_intern 12 Mei 2021, 06:47