prolog - prolog中一组N维向量的最小支配向量

Question

我需要编写一个程序，为一组 N 维向量构造一个最小支配向量。向量集合 S 的支配向量被定义为第 i 个分量大于或等于 S 中每个向量的第 i 个分量的向量，其中 i 分布在向量的所有维度上。维度 N 必须作为用户的输入。

Answer 1

串行实现：

fnt(M,N) :-
    fnt2(M,N,0,[]).

fnt2(_,N,N,Ds) :-
    reverse(Ds,R),
    write(R).
fnt2(M,N,K,Ds) :-
    column(M,K,Col),
    max_list(Col,H),
    K2 is K+1,
    fnt2(M,N,K2,[H|Ds]).


row(M, N, Row) :-
    nth(N, M, Row).

column(M, N, Col) :-
    transpose(M, MT),
    row(MT, N, Col).

symmetrical(M) :-
    transpose(M, M).

transpose([[]|_], []) :- !.
transpose([[I|Is]|Rs], [Col|MT]) :-
    first_column([[I|Is]|Rs], Col, [Is|NRs]),
    transpose([Is|NRs], MT).

first_column([], [], []).
first_column([[]|_], [], []).
first_column([[I|Is]|Rs], [I|Col], [Is|Rest]) :-
    first_column(Rs, Col, Rest).

nth(0,[X|_],X).
            nth(N,[_|T],R):- M is N-1,nth(M,T,R).

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

并行实现（小调整）

fnt(M,N) :-
    fnt2(M,N,0,[]).

fnt2(_,N,N,Ds) :-
    reverse(Ds,R),
    write(R).
fnt2(M,N,K,Ds) :-
    column(M,K,Col),
    max_list(Col,H),
    K2 is K+1,
    fork(fnt2(M,N,K2,[H|Ds])).


row(M, N, Row) :-
    nth(N, M, Row).

column(M, N, Col) :-
    transpose(M, MT),
    row(MT, N, Col).

symmetrical(M) :-
    transpose(M, M).

transpose([[]|_], []) :- !.
transpose([[I|Is]|Rs], [Col|MT]) :-
    first_column([[I|Is]|Rs], Col, [Is|NRs]),
    transpose([Is|NRs], MT).

first_column([], [], []).
first_column([[]|_], [], []).
first_column([[I|Is]|Rs], [I|Col], [Is|Rest]) :-
    first_column(Rs, Col, Rest).

nth(0,[X|_],X).
            nth(N,[_|T],R):- M is N-1,nth(M,T,R).

max_list([H], H).
max_list([H|T], M2) :- 
  max_list(T, M),
  M2 is max(H, M).

reverse(A,R) :- reverse(A,[],R).
reverse([X|Y],Z,W) :- reverse(Y,[X|Z],W).
reverse([],X,X).

测试：

time(fnt([[1,2,3,56],[14,5,6,43],[7,8,9,22]],4)).

Answer 2

Prolog 没有向量。您可以使用列表或 arity N 的结构。当然，在第二种情况下，N 必须小于允许的最大 arity（SWI-Prolog 具有无限长度......）

如果您使用列表，则此代码应该可以。我假设 N 是从列表长度中隐含的。

'minimal dominating vector'([V|Vs], Min) :-
  'minimal dominating vector'(Vs, V, Min).

'minimal dominating vector'([], M, M).
'minimal dominating vector'([V|Vs], MinSoFar, Min) :-
   maplist(min, V, MinSoFar, Updated),
   'minimal dominating vector'(Vs, Updated, Min).

min(X, Y, M) :- X < Y -> M = X ; M = Y.

测试：

?- 'minimal dominating vector'(["abc","aab","uaa"],M),format('~s',[M]).
aaa
M = [97, 97, 97].

如果您的 Prolog 没有 maplist/4（我不记得 P# 的这个细节），那么替换maplist(min, V, MinSoFar, Updated),为minvect(V, MinSoFar, Updated),，并添加这个定义

minvect([], [], []).
minvect([N|Ns], [M|Ms], [R|Rs]) :- min(N,M,R), !, minvect(Ns,Ms,Rs).

请注意，OT一年前我尝试 P# 时，发现它非常慢，而且内存不足。如果你有大数组，那么你最好使用 LINQ