2

编写一个谓词，将整数列表作为输入L，并生成两个列表：包含来自L的偶数元素的列表和来自 的奇数元素的列表L。

?- separate_parity([1,2,3,4,5,6], Es, Os).
Es = [2,4,6], Os = [1,3,5] ? ;
no
4

4 回答 4

5

只需在列表上使用结构递归。写下每个互斥情况的等价关系：

parity_partition([A|B], [A|X], Y):- 0 is A mod 2, parity_partition(B,X,Y).
parity_partition([A|B], X, [A|Y]):- 1 is A mod 2, parity_partition(B,X,Y).
parity_partition([],[],[]).

这意味着：关系parity_partition(L,E,O) 成立，

  1. 如果L=[A|B]和A是偶数，当和 关系成立。E=[A|X]O=Yparity_partition(B,X,Y)
  2. 如果L=[A|B]和A是奇数，当和 关系成立。E=XO=[A|Y]parity_partition(B,X,Y)
  3. 万一L=[]，当E=[]和O=[]。

只要写下这些等价，我们就可以使用 Prolog 程序来解决这个问题。

在操作上，这意味着：将列表L分为偶数E列表和赔率列表O，

  1.如果`L`是一个非空列表`[A|B]`，
     1a。如果 `A` 是偶数，
              为`E=[H|T]`分配新的列表节点，
              设置其数据字段“H=A”，
              并继续分离输入列表的其余部分“B”
                           进入 `T` 和 `O` ; 或者
     1b。如果`A`是奇数，
              为 `O=[H|T]` 分配新的列表节点，
              设置其数据字段“H=A”，
              并继续分离输入列表的其余部分“B”
                           进入 `E` 和 `T` ; 或者
  2.如果`L`是一个空列表，将`E`和`O`都设置为空列表

实际的操作顺序可能有点不同，但在概念上是相同的：

  1.尽量统一L=[A|B], E=[A|X]。如果没有，请转到 2。
     1a。检查A是否是偶数。
         如果没有，请放弃所做的实例化
                 作为统一的一部分，然后转到 2。
     1b。继续使用 B、X 和相同的 O：使用 B 作为 L，使用 X 作为 E，然后转到 1。
  2.尝试统一L=[A|B]，O=[A|Y]。如果没有，请转到 3。
     2a. 检查 A 是否为奇数。
         如果没有，请放弃所做的实例化
                 作为统一的一部分，然后转到 3。
     2b。继续使用 B、Y 和相同的 E：使用 B 作为 L，使用 Y 作为 O，然后转到 1。
  3. 用 [] 统一 L,E,O。
于 2013-01-14T13:40:01.570 回答
3

您可以为此使用。通过这种方式，你得到一个纯粹的关系：

:- use_module(library(clpfd)).
list_evens_odds([], [], []).
list_evens_odds([E|Zs], [E|Es], Os) :-
   0 #= E mod 2,
   list_evens_odds(Zs, Es, Os).
list_evens_odds([E|Zs], Es, [E|Os]) :-
   1 #= E mod 2,
   list_evens_odds(Zs, Es, Os).

您不仅可以使用它来将列表拆分为偶数和赔率。但你可以走得更远。以下交互是使用 SWI 进行的，但您在 SICStus 中使用asserta(clpfd:full_answer).

?- list_evens_odds([1, 2, 3, 4, 5, 6], Es, Os)。
Es = [2, 4, 6],
os = [1, 3, 5] ;
错误的。

?- Zs = [A,B,C], list_evens_odds(Zs, Es, Os)。
Zs = [A, B, C],
Es = [A, B, C],
奥斯= []，
一个 mod 2#=0,
B mod 2#=0,
C mod 2#=0 ;
Zs = [A, B, C],
Es = [A, B],
奥斯= [C]，
一个 mod 2#=0,
B mod 2#=0,
C mod 2#=1 ;
Zs = [A, B, C],
Es = [A, C],
奥斯= [B]，
一个 mod 2#=0,
B mod 2#=1,
C mod 2#=0 ...

?- Es = [E], Os = [O], list_evens_odds(Zs, Es, Os)。
Es = [E]，
奥斯 = [O]，
Zs = [E, O],
E mod 2#=0,
O mod 2#=1 ;
Es = [E]，
奥斯 = [O]，
Zs = [O, E],
E mod 2#=0,
O mod 2#=1 ;
错误的。

接下来可能是最烦人的：在这里，我们询问是否存在一个EO既是偶数又是奇数的整数。当然，这样的整数是不可能存在的。但我们仍然得到两个答案！

?- EOs=[EO], list_evens_odds(Zs, EOs, EOs)。
EO = [EO]，
Zs = [EO，EO]，
EO mod 2#=1,
EO mod 2#=0 ;
EO = [EO]，
Zs = [EO，EO]，
EO mod 2#=0,
EO mod 2#=1 ;
错误的。

这说明了答案和解决方案之间的区别。我们在这里得到两个答案，但两者都不包含解决方案。大多数情况下，答案包含一个或多个解决方案，但也可以不包含任何解决方案，就像在这种情况下一样。这样的答案有时被称为不一致。

不一致不一定被认为是实现的错误。它们是一种工程折衷：与实际收益相比，确保一致性的成本可能非常高。并且： Prolog 不会产生不正确的答案：对于必须保持的条件已显示。即使那个条件被证明是错误的。

于 2013-01-14T14:21:27.227 回答
3

此答案基于、 tpartition/4和 reified test zodd_t/2：

:- use_module(library(clpfd)).

tpartition/4结合使用我们zodd_t/2可以简单地写：

?- tpartition(zodd_truth,[1,2,3,4,5,6],Es,Os).
Es = [1,3,5], Os = [2,4,6].                 % succeeds deterministically
于 2015-10-10T15:31:35.183 回答
1

@Will Ness 的回答很好而且很详细。如果您的 Prolog 提供它，我将添加使用“高阶”内置函数的可能性（即接收谓词作为参数的谓词）：

separate_parity(L, E, O) :-
    partition(is_even, L, E, O).
is_even(N) :- N mod 2 =:= 0.

您可以在此处找到内置函数的简要说明。

于 2013-01-14T14:03:17.757 回答