Prolog:按奇偶校验对整数列表项进行分区 [英] Prolog: partition integer list items by their parity

问题描述

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

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

解决方案

只需在列表上使用结构递归.写下每个互斥情况的等价:

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

这意味着:relation parity_partition(L,E,O) holds,

1. 如果 L=[A|B] 和 A 是偶数，when E=[A|X]、O=Y 和关系 parity_partition(B,X,Y) 成立.
2. 如果 L=[A|B] 和 A 是奇数，when E=X，O=[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.

Write a predicate which takes as input a list of integers, L, and produces two lists: the list containing the even elements from L and the list of odd elements from L.

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

解决方案

Just use structural recursion on lists. Write down the equivalences for each mutually exclusive case:

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([],[],[]).

This means: relation parity_partition(L,E,O) holds,

1. in case L=[A|B] and A is even, when E=[A|X], O=Y and relation parity_partition(B,X,Y) holds.
2. in case L=[A|B] and A is odd, when E=X, O=[A|Y] and relation parity_partition(B,X,Y) holds.
3. in case L=[], when E=[] and O=[].

Just writing down these equivalences gives us the Prolog program to solve this.

---

Operationally, this means: to separate a list L into a list of evens E and a list of odds O,

  1. if `L` is a non-empty list `[A|B]`,
     1a.  if `A` is even, 
              allocate new list node for `E=[H|T]`, 
              set its data field `H=A`,
              and continue separating the rest of input list `B`
                           into `T` and `O` ; or
     1b.  if `A` is odd, 
              allocate new list node for `O=[H|T]`, 
              set its data field `H=A`,
              and continue separating the rest of input list `B`
                           into `E` and `T` ; or
  2. if `L` is an empty list, set both `E` and `O` to be empty lists

the actual sequence of operations might be a little bit different but conceptually the same:

  1. try to unify L=[A|B], E=[A|X]. If not, go to 2. 
     1a. check if A is even. 
         If not, abandon the instantiations made 
                 as part of unifications, and go to 2.
     1b. Continue with B, X, and the same O: use B as L, X as E, and go to 1.
  2. try to unify L=[A|B], O=[A|Y]. If not, go to 3.
     2a. check if A is odd. 
         If not, abandon the instantiations made 
                 as part of unifications, and go to 3.
     2b. Continue with B, Y, and the same E: use B as L, Y as O, and go to 1.
  3. Unify L,E,O with [].

这篇关于Prolog:按奇偶校验对整数列表项进行分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！