创建一个交错元素列表：Prolog

Question

我正在定义一个名为alternate_func（Ps，P）的函数，其中Ps是一个列表的列表，而P是Ps中所有元素的列表，其行为如下：

?- alternate_func([[p,q],[r,s]],P). 
P=[p,r,q,s]. (case 1)

?- alternate_func([P,Q,R],[p,q,r,s,t,u]). 
P=[p,s], Q=[q,t], R=[r,u]. (case 2)

?- alternate_func([Q],[1,2,3]). 
Q=[1,2,3]. (case 3)

?- alternate_func([[4,5,6],[3,1],[4,1,2]],X).
false. (because Length of sublists must be same) (case 4)

这是我迄今为止尝试过的内容：

alternate_func([[], L], L).          
alternate_func([[H|T], []], [H|T]).  

alternate_func([[X|L1], [Y|L2]], [X,Y|L3]) :-
    alternate_func([L1, L2], L3).

我能正确获取第1个案例的结果，但对于第2、3和4个案例失败了。这里的问题是什么？

- Katherine

---

所有子列表都必须具有相同的长度吗？ - false

是的，它们必须具有相同的长度。 - Katherine

Answer 1

这个方案处理了一个列表的列表并将每个列表的头部/尾部分离。结果如下:

• 如果所有的尾部都是空的，那么我们就完成了。
• 否则，该过程将再次重复，使用尾部。

代码:

lists_interleaved( Ess, Es):-
  lists_interleaved( Ess, X-X, Es).

lists_interleaved( [], Head-[], []):-
  maplist(=([]), Head).
lists_interleaved( [], [First|Head]-[], Es):-
  lists_interleaved( [First|Head], X-X, Es).
lists_interleaved( [[E|ETail]|Ess], Head-[ETail|Rest], [E|Es]):-
  lists_interleaved( Ess, Head-Rest, Es).

- gusbro

---

@Katherine X-X 和 -(X,X) 是相同的，也就是 p(X,X) 或者 q(X,X) 等等，其中 -、p、q 或其他名称都是任意的。它只是一个包含两个参数的复合术语，用中缀符号表示。 - Will Ness

@Katherine，这是我对这段代码的重新编写（https://gist.github.com/WillNess/0b6f19cea9b084d129bb0af1b048106c#file-so-55795221-md），看看是否更容易理解。 :) - Will Ness

is_prime(N)：- length(L，N)，findall(X，lists_interleaved(X，L)，[,])。 - Will Ness

@WillNess：有趣的观察... 经过一番思考，这是有道理的。 - gusbro

另一个例子：factors(Num,M*N):- length(L,Num), lists_interleaved( X, L), maplist(length,X,[M|_]), length(X,N). :) --- 但这当然是一种非常迂回的方式，与 factors(Num, M*N):- findall(A, between(1,Num, A),As), reverse(As,Bs), member(M,Bs), N is Num div M, Num is M*N. 做的事情完全相同...... - Will Ness

Answer 2

首先，保持关系的良好命名。这里没有function。您有一个列表和列表之间的关系，因此最好使用名称lists_interleaved(Ess, Es)。

:- set_prolog_flag(double_quotes, chars).  % to permit that "abc" = [a,b,c]

lists_interleaved(Ess, Es) :-
   transpose(Ess, EssT),
   phrase(seqq(EssT), Es).          % alternatively append(EssT,Es)

查看seqq//1的定义。

尽管如此，这不是最好的定义。毕竟，?- lists_interleaves(Ess, "abcd").不会终止。让我们使用failure-slice来查看原因：

lists_interleaved(Ess, Es) :-
   transpose(Ess, EssT), false,
   phrase(seqq(EssT), Es).
?- lists_interleaved(Ess, "abcd"), false.
   循环。

修复这个问题的简单方法是建立Ess和Es之间的关系。 毕竟，Ess中的第一个列表最多只能与Es一样长，并且Ess不能更长。

通过将这些限制作为额外的目标添加，我们得到：

lists_interleaved(Ess, Es) :-
   Ess = [Fs|_],
   Fs = [_|_],
   list_longer(Ess, Es),
   list_longer(Fs, Es),
   transpose(Ess, EssT),
   phrase(seqq(EssT), Es).

list_longer([], _).
list_longer([_|Es], [_|Fs]) :-
   list_longer(Es, Fs).

这将限制我们至少有一个元素的Es。

?- lists_interleaved(Ess, "abcdef").
   Ess = ["abcdef"]
;  Ess = ["ace","bdf"]
;  Ess = ["ad","be","cf"]
;  Ess = ["a","b","c","d","e","f"]
;  false.

请查看此答案，了解如何使用紧凑的双引号符号打印解决方案。

尽管如此，这仍然不完美，因为这些list_longer/2目标现在基本上是猜测。但我会保持原样，因为这是您要求的。

（我将为更好的定义/或证明为什么这不可能提供赏金）

- false

---

嗨，感谢回复。对于第一种情况，我的结果是 P = [_16262, _16268|_16270]。现在，使用您的代码，其余的情况也失败了。我不觉得引号有问题，我的早期代码可以正常运行第一种情况。您能帮我解决一下吗？ - Katherine

你可能已经将改进版本作为单独的规则添加了。为了避免任何歧义，我现在提供了整个程序。当然，你所有的情况都可以工作。甚至更好！情况 lists_interleaved(Ess, "abcdef"). 比你要求的情况更一般化。 - false

嗨，我明白了自己做错了什么。我一开始得到了Undefined procedure: transpose/2和Undefined procedure: seqq/3的错误提示，于是我使用在swipl-devel/clpfd.pl中找到的定义来对它们进行了定义。接着，程序在四个测试用例中有三个通过了。但是，在第二个测试用例中还是出现了Arguments are not sufficiently instantiated的错误。 - Katherine

请使用 clpfd:lists_transpose(Ess, EssT)。这个版本有太多的错误检查。 - false