如何将前N个元素移到列表的末尾 [英] How to move first N elements to the end of the list

问题描述

我想知道如何将列表中的前N个元素移到最后. 例如:

I am wondering how can I move first N elements from a list and put them at the end. For example:

[1,2,3,4]，我想移动前2个元素，所以结果将是[3,4,1,2].

[1,2,3,4] and I want to move first 2 elements , so the result will be [3,4,1,2].

rule(List1,N,List2) :- length(List1,Y), ...

我不知道如何开始，有什么建议吗?

I don't know how to start, any advice ?

推荐答案

您可以选择对任务采用更一般的观点.如果考虑一下，将列表的前N个元素附加到末尾可以看作是向左旋转了N步(假设列表元素排列成一个圆圈). @Willem Van Onsem的答案中的谓词名称rotate/3也表明了这种观点.实际上，您可以将这样的谓词定义为真正的关系，即谓词可以在所有方向上起作用.另外，希望避免对参数施加不必要的限制，同时保留良好的终止属性.为了反映谓词的关系性质，我们选择一个描述性名称.由于第三个参数是列表的N步(第一个参数)向左旋转，因此我们可以将其称为list_n_lrot/3并按如下方式定义它:

You could opt to adopt a more general perspective on the task. If you think about it, taking the first N elements of a list and appending them at the end can be seen as a rotation to the left by N steps (just imagine the list elements arranged in a circle). The predicate name rotate/3 in @Willem Van Onsem's answer also indicates this perspective. You can actually define such a predicate as a true relation, that is making it work in all directions. Additionally it would be desirable to abstain from imposing unnecessary restrictions on the arguments while retaining nice termination properties. To reflect the relational nature of the predicate, let's choose a descriptive name. As the third argument is the left rotation by N steps of the list that is the first argument, let's maybe call it list_n_lrot/3 and define it like so:

:- use_module(library(lists)).
:- use_module(library(clpfd)).

list_n_lrot([],0,[]).                 % <- special case
list_n_lrot(L,N,LR) :-
   list_list_samelength(L,LR,Len),    % <- structural constraint
   NMod #= N mod Len,
   list_n_heads_tail(L,NMod,H,T),
   append(T,H,LR).

list_list_samelength([],[],0).
list_list_samelength([_X|Xs],[_Y|Ys],N1) :-
   N1 #> 0,
   N0 #= N1-1,
   list_list_samelength(Xs,Ys,N0).

list_n_heads_tail(L,N,H,T) :-
   if_(N=0,(L=T,H=[]),
           (N0#=N-1,L=[X|Xs],H=[X|Ys],list_n_heads_tail(Xs,N0,Ys,T))).

现在让我们逐步了解该定义，并通过示例观察其一些影响. list_n_lrot/3的第一条规则仅用于处理空列表的特殊情况:

Now let's step through the definition and observe some of its effects by example. The first rule of list_n_lrot/3 is only included to deal with the special case of empty lists:

?- list_n_lrot([],N,R).
N = 0,
R = [] ;
false.

?- list_n_lrot(L,N,[]).
L = [],
N = 0 ;
false.

?- list_n_lrot(L,N,R).
L = R, R = [],
N = 0 ;
...

如果您不想在解决方案中包括这些情况，则可以忽略该规则.整个谓词CLP(FD)都用于算术约束，因此list_n_lrot/3的第二个参数可以可变，而不会导致实例化错误.目标list_list_samelength/2是确保两个列表长度相同的结构约束.这有助于在仅第三个参数为基础的情况下避免在产生所有答案后出现无限循环(要看到这一点，请删除list_n_lrot/3的前两个目标并将第三个目标替换为list_n_heads_tail(L,N,H,T)，然后尝试查询?- list_n_lrot(L,N,[1,2,3]). ).这也是最常见的查询按公平顺序列出解决方案的原因，即为每个列表长度生成所有可能性，而不是仅按0步列出轮换:

If you don't want to include these cases in your solution just omit that rule. Throughout the predicates CLP(FD) is used for arithmetic constraints, so the second argument of list_n_lrot/3 can be variable without leading to instantiation errors. The goal list_list_samelength/2 is a structural constraint to ensure the two lists are of same length. This helps avoiding an infinite loop after producing all answers in the case that only the third argument is ground (to see this, remove the first two goals of list_n_lrot/3 and replace the third with list_n_heads_tail(L,N,H,T) and then try the query ?- list_n_lrot(L,N,[1,2,3]).). It's also the reason why the most general query is listing the solutions in a fair order, that is producing all possibilities for every list length instead of only listing the rotation by 0 steps:

?- list_n_lrot(L,N,R).
...                                   % <- first solutions
L = R, R = [_G2142, _G2145, _G2148],  % <- length 3, rotation by 0 steps
N mod 3#=0 ;
L = [_G2502, _G2505, _G2508],         % <- length 3, rotation by 1 step
R = [_G2505, _G2508, _G2502],
N mod 3#=1 ;
L = [_G2865, _G2868, _G2871],         % <- length 3, rotation by 2 steps
R = [_G2871, _G2865, _G2868],
N mod 3#=2 ;
...                                   % <- further solutions

最后，它还描述了两个列表的实际长度，在下一个目标中使用它来确定N的余数，以列表的长度为模.请考虑以下情况:如果将长度为N的列表旋转N步，则会再次到达初始列表.因此，旋转N + 1步将产生与旋转1步相同的列表.从代数角度来讲，该目标是利用同余模N将无限整数集划分为有限数量的残差类的事实.因此，对于长度为N的列表，产生与N个残基类别相对应的N个旋转就足够了，以覆盖所有个可能的旋转(请参阅上面的查询，其中N = 3).另一方面，给定的 N>列表长度可以很容易地通过选择其残基类别中最小的非负成员来计算.例如，给定一个包含三个元素的列表，分别旋转2步或5步将产生相同的结果:

Finally, it also describes the actual length of the two lists, which is used in the next goal to determine the remainder of N modulo the length of the list. Consider the following: If you rotate a list of length N by N steps you arrive at the initial list again. So a rotation by N+1 steps yields the same list as a rotation by 1 step. Algebraically speaking, this goal is exploiting the fact that congruence modulo N is partitioning the infinite set of integers into a finite number of residue classes. So for a list of length N it is sufficient to produce the N rotations that correspond to the N residue classes in order to cover all possible rotations (see the query above for N=3). On the other hand, a given N > list length can be easily computed by taking the smallest non-negative member of its residue class. For example, given a list with three elements, a rotation by 2 or 5 steps respectively yields the same result:

?- list_n_lrot([1,2,3],2,R).
R = [3, 1, 2].

?- list_n_lrot([1,2,3],5,R).
R = [3, 1, 2].

当然，您还可以将列表旋转负数步，即朝另一个方向旋转:

And of course you could also left rotate the list by a negative number of steps, that is rotating it in the other direction:

?- list_n_lrot([1,2,3],-1,R).
R = [3, 1, 2].

附带说明:由于这构成了向右旋转，因此您只需编写以下内容即可轻松定义向右旋转:

list_n_rrot(L,N,R) :-
   list_n_lrot(L,-N,R).

?- list_n_rrot([1,2,3],1,R).
R = [3, 1, 2].

谓词list_n_heads_tail/4与Willem帖子中的splitAt/4非常相似.但是，由于使用了 if_/3 ，该谓词可以确定性地成功(唯一答案后无需点击; (因为没有多余的选择点会保留)，如果列表之一和list_n_lrot/3的第二个参数为空:

The predicate list_n_heads_tail/4 is quite similar to splitAt/4 in Willem's post. However, due to the use of if_/3 the predicate succeeds deterministically (no need to hit ; after the only answer since no unnecessary choicepoints are left open), if one of the lists and the second argument of list_n_lrot/3 are ground:

?- list_n_lrot2([a,b,c,d,e],2,R).
R = [c, d, e, a, b].

?- list_n_lrot2(L,2,[c,d,e,a,b]).
L = [a, b, c, d, e].

您可以在最一般的查询的第二个解决方案中看到使用CLP(FD)的另一个不错的效果:

You can observe another nice effect of using CLP(FD) with the second solution of the most general query:

?- list_n_lrot(L,N,R).
L = R, R = [],
N = 0 ;
L = R, R = [_G125],       % <- here
N in inf..sup ;           % <- here
...

此答案指出，对于一个元素只有一个列表的任何旋转任意步数的列表，都将再次生成完全相同的列表.因此，原则上，这个单一的一般性答案总结了无限数量的具体答案.此外，您还可以提出以下问题:关于2步轮换，有哪些列表?

This answer states, that for a list with one element any rotation by an arbitrary number of steps yields the very same list again. So in principle, this single general answer summarizes an infinite number of concrete answers. Furthermore, you can also ask questions like: What lists are there with regard to a rotation by 2 steps?

?- list_n_lrot2(L,2,R).
L = R, R = [_G19] ;
L = R, R = [_G19, _G54] ;
L = [_G19, _G54, _G22],
R = [_G22, _G19, _G54] ;
...

最后回到您问题中的示例:

To finally come back to the example in your question:

?- list_n_lrot([1,2,3,4],2,R).
R = [3, 4, 1, 2].

请注意，这种在列表上定义任意旋转的更通用方法是如何包含将前N个元素重新定位到列表末尾的用例.

Note how this more general approach to define arbitrary rotations on lists subsumes your use case of relocating the first N elements to the end of the list.

这篇关于如何将前N个元素移到列表的末尾的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！