rub*_*ops 9 tuples list prolog
我正试图用Prolog解决一个新程序,我被卡住了,不知道如何继续...我必须做一个有3个参数的谓词,第一个是元素列表,第二个是是元组列表,如果元组的第一个元素与第一个参数列表的元素匹配,则第三个必须是返回的包含元组的第二个元素的列表.它也必须删除副本!!
例如,
check([a,c],[(a,aa),(bb,bbb),(a,aa),(c,def)],X).
X = [aa, def] .
如您所见,a和c匹配元组列表,因此返回元组的第二个元素.
所以它可以工作,但如果有多个元组包含第一个匹配的第一个元素,它只需要一次,例如:
check([a,b],[(a,c),(a,d),(b,c),(b,e),(c,f)],X).
X = [c] .
它第一次找到并且第一次取c和b,再次取c,但不迭代找到更多的a或b,正确的结果应该是X = [c,d,e].
所以,请问您如何解决这种情况或解决问题的任何线索......
这是我的代码:
check([],_,[]).
check(L,DIC,Xord) :- inter(L,DIC,X), list_to_set(X,Xord).
inter([],_,[]).
inter(L1, DIC, L3) :-
L1 = [H|T],
DIC = [(DIC1,DIC2)|_],
H == DIC1,
L3 = [DIC2|L3T],
inter(T, DIC, L3T).
inter(L1,[_|DIC],L3) :- inter(L1,DIC,L3).
inter([_|T], DIC, L3) :- inter(T, DIC, L3).
在此先感谢您的时间.
为了更容易理解的版本,我提出以下建议:
:- use_module(library(lists)).
keys_dict_uniquevalues(Ks,D,UVs) :-
keys_dict_values(Ks,D,Vs), % Vs ... values with duplicates
list_set(Vs,UVs). % UVs ... Vs deduplicated
keys_dict_values([],_D,[]). % No keys no values
keys_dict_values([Key|Keys],D,Vs) :-
key_dict_values(Key,D,Matches), % all Matches for Key
keys_dict_values(Keys,D,OtherVs), % Matches for other Keys
append(Matches,OtherVs,Vs). % all found values in Vs
key_dict_values(_K,[],[]). % no mathes if dictionary empty
key_dict_values(K,[(K,V)|Pairs],[V|Vs]) :- % Value is in list if key matches
key_dict_values(K,Pairs,Vs).
key_dict_values(K,[(X,_V)|Pairs],Vs) :- % Value is not in list
dif(K,X), % if key doesn't match
key_dict_values(K,Pairs,Vs).
list_set([],[]). % empty list contains no duplicates
list_set([X|Xs],[X|Ys]) :- % head of the first list
subtract(Xs,[X],Zs), % doesn't occur in Zs
list_set(Zs,Ys).
如果你想在不使用库(列表)的情况下编写程序,则必须替换keys_dict_values/3中的目标append/3和list_set/2中的目标减去/ 3.在下面的例子中,list_appended/3和list_x_removed/3:
keys_dict_uniquevalues(Ks,D,UVs) :-
keys_dict_values(Ks,D,Vs),
list_set(Vs,UVs).
keys_dict_values([],_D,[]).
keys_dict_values([Key|Keys],D,Vs) :-
key_dict_values(Key,D,Matches),
keys_dict_values(Keys,D,OtherVs),
lists_appended(Matches,OtherVs,Vs).
key_dict_values(_K,[],[]).
key_dict_values(K,[(K,V)|Pairs],[V|Vs]) :-
key_dict_values(K,Pairs,Vs).
key_dict_values(K,[(X,_V)|Pairs],Vs) :-
dif(K,X),
key_dict_values(K,Pairs,Vs).
lists_appended([],L,L).
lists_appended([X|Xs],Ys,[X|Zs]) :-
lists_appended(Xs,Ys,Zs).
list_set([],[]).
list_set([X|Xs],[X|Ys]) :-
list_x_removed(Xs,X,Zs),
list_set(Zs,Ys).
list_x_removed([],_X,[]).
list_x_removed([X|Xs],X,Ys) :-
list_x_removed(Xs,X,Ys).
list_x_removed([X|Xs],Z,[X|Ys]) :-
dif(X,Z),
list_x_removed(Xs,Z,Ys).
上述例外中给出的查询适用于两个版本:
?- keys_dict_uniquevalues([a,c],[(a,aa),(bb,bbb),(a,aa),(c,def)],X).
X = [aa,def] ? ;
no
?- keys_dict_uniquevalues([a,b],[(a,c),(a,d),(b,c),(b,e),(c,f)],L).
L = [c,d,e] ? ;
no
@false提供的反例对于两个版本均未按预期进行:
?- keys_dict_uniquevalues([a,b],[(a,c),(a,d),(b,c),(b,e),(c,f)],[c,c]).
no
@false建议的不寻常用法:
?- keys_dict_uniquevalues([a,b],[KV1,KV2],[e]).
KV1 = KV2 = (a,e) ? ;
KV1 = (a,e),
KV2 = (b,e) ? ;
KV1 = (a,e),
KV2 = (_A,_B),
dif(b,_A),
dif(a,_A) ? ;
KV1 = (b,e),
KV2 = (a,e) ? ;
KV1 = (_A,_B),
KV2 = (a,e),
dif(b,_A),
dif(a,_A) ? ;
KV1 = KV2 = (b,e) ? ;
KV1 = (b,e),
KV2 = (_A,_B),
dif(b,_A),
dif(a,_A) ? ;
KV1 = (_A,_B),
KV2 = (b,e),
dif(b,_A),
dif(a,_A) ? ;
no
到目前为止,您的问题陈述和随后的解释有点矛盾.让我们看看这是否合适.
作为第一个,尝试将您的问题描述为关系,而不是作为一系列操作或命令.为了更好地概述这一点,尝试找到一个不建议必须完成某些事情的关系的名称.相反,逐个描述每个参数.你在评论中对此赞不绝口,并注意到"这只是一个名字".当然,只是一个名字.但这就是程序员所拥有的.全名.如果每个名字都是任意选择的,甚至是误导你将会有一个非常艰难的时间编程.
那么你有什么:
包含元素的列表keys.注意这keys是复数.在Prolog中,许多复数代表名单.
一些字典,或dict带(K, V)元素.实际上,在Prolog中,我们更常使用,(K-V)并将其称为a pair,因此pairs也非常合适.但是让我们坚持你的定义.
值列表.该清单不具备重复数据.我们可以将其称为唯一值列表,或者uvalues.
现在所有这一切都有一个很好的关系:
keys_dict_uvalues(Keys, Dict, UValues)
在急于实际编码之前,只需想象您已经编写过它,现在就想使用它.或者:也许你会找到一个会为你编写谓词的人.但是,如何确保代码正常工作？所以一起收集一些测试用例.最好从地面查询开始:
?- keys_dict_uniquevalues([a,c],[(a,aa),(bb,bbb),(a,aa),(c,def)],[aa,def]).
鉴于此,我们可以通过引入变量来省略某些部分:
?- keys_dict_uniquevalues([K1,K2],[(a,aa),(bb,bbb),(a,aa),(c,def)],[aa,def]).
你期望在这里有多少解决方案？我认为这只是一个.当然？在那个时间点,这些考虑是非常有价值的.
但现在为编码.我经常喜欢自上而下的方法:
keys_dict_uniquevalues(Ks, KVs, Vsu) :-
keys_dict_values(Ks, KVs, Vs),
list_nub(Vs, Vsu).
keys_dict_values(Ks, KVs, Vs) :-
maplist(list_pmemberv(KVs), Ks, Vs).
list_pmemberv(KVs, K, V) :- % the first fitting K
tmember(k_v_p_t(K,V), KVs).
k_v_p_t(K, V, (Ki, Vi), T) :-
if_(K = Ki, ( Vi = V, T = true ), T = false).
list_nub([], []).
list_nub([E|Es], [E|Gs]) :-
tfilter(dif(E), Es, Fs),
list_nub(Fs, Gs).
上述用途的其他例子定义了一些定义:
maplist/3,
if_/3,
tmember/2,
tfilter/3,
(=)/3,
dif/3.
以下是一些相当不寻常的例子:
如何必须以两个项目的字典看起来像这样
a和b都映射到e？
?- keys_dict_uniquevalues([a,b],[KV1,KV2],[e]).
KV1 = (a,e),
KV2 = (b,e) ? ;
KV1 = (b,e),
KV2 = (a,e) ? ;
no
所以有两种可能性.
再想一想,这种关系实际上是关于列表的,因此是DCG的优秀候选者:
keys_dict_uniquevalues(K,D,UVs) :-
phrase(keys_values(K,D),Vs),
phrase(uniques(Vs),UVs).
keys_values([],_D) --> % no keys no values
[].
keys_values([K|Keys],D) -->
key_values(K,D), % the values for key K
keys_values(Keys,D). % followed by values for other keys
key_values(_K,[]) --> % no values left for key _K
[].
key_values(K,[(K2,V)|Pairs]) --> % values for
{dif(K,K2)}, % different keys are not in the list
key_values(K,Pairs).
key_values(K,[(K,V)|Pairs]) --> % values for en equal key
[V], % are in the list
key_values(K,Pairs).
uniques([]) --> % the empty list has no duplicates
[].
uniques([X|Xs]) -->
[X], % X is in the list
{phrase(list_without(Xs,X),XRs)}, % once
uniques(XRs).
list_without([],_X) --> % no X in the empty list
[].
list_without([X|Xs],X) --> % X is not in the list
list_without(Xs,X).
list_without([Y|Ys],X) -->
[Y], % Y is in the list
{dif(X,Y)}, % if it is different from X
list_without(Ys,X).
我觉得这个版本比我的非DCG版本更容易阅读(参见代码中的注释).两个版本的界面都是相同的,因此我的上述查询与此版本一对一地工作.查询
?- keys_dict_uniquevalues([a,b],[KV1,KV2],[e]).
也以相反的顺序产生相同的结果.
| 归档时间： |
|
| 查看次数： |
3530 次 |
| 最近记录： |