Prolog程序：从列表中删除每个第n个元素。

Question

你能帮我解决以下问题吗？

编写一个三元谓词delete_nth，从列表中删除每个第n个元素。

样例运行：

?‐ delete_nth([a,b,c,d,e,f],2,L).
L = [a, c, e] ;
false
?‐ delete_nth([a,b,c,d,e,f],1,L).
L = [] ;
false
?‐ delete_nth([a,b,c,d,e,f],0,L).
false

我尝试了这个：

listnum([],0).
listnum([_|L],N) :-
   listnum(L,N1),
   N is N1+1.

delete_nth([],_,_).
delete_nth([X|L],C,L1) :- 
   listnum(L,S),
   Num is S+1,
   (  C>0
   -> Y is round(Num/C),Y=0
   -> delete_nth(L,C,L1)
   ;  delete_nth(L,C,[X|L1])
   ).

- user3598120

Answer 1

我稍微有些奢华的变体：

delete_nth(L, N, R) :-
    N > 0, % Added to conform "?‐ delete_nth([a,b,c,d,e,f],0,L). false"
    ( N1 is N - 1, length(Begin, N1), append(Begin, [_|Rest], L) ->
        delete_nth(Rest, N, RestNew), append(Begin, RestNew, R)
    ;
        R = L
    ).

- Sergii Dymchenko

Answer 2

让我们使用 clpfd！出于通用性和其他许多好的原因：

:- use_module(library(clpfd)).

我们基于if_/3和(#>=)/3定义delete_nth/3函数：

delete_nth(Xs,N,Ys) :-
   N #> 0,
   every_tmp_nth_deleted(Xs,0,N,Ys).

every_tmp_nth_deleted([]    ,_ ,_,[] ).     % internal auxiliary predicate
every_tmp_nth_deleted([X|Xs],N0,N,Ys0) :-
   N1 is N0+1,
   if_(N1 #>= N,
       (N2 =  0, Ys0 =    Ys ),
       (N2 = N1, Ys0 = [X|Ys])),
   every_tmp_nth_deleted(Xs,N2,N,Ys).

示例查询：

？- delete_nth（[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]，2，Ys）。
Ys = [1,3,5,7,9,11,13,15]                 ％成功确定性地

好的，那么再来点更一般化的东西怎么样？

?- delete_nth([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],N,Ys). 当 N = 1 时， Ys = [] ; 当 N = 2 时， Ys = [1, 3, 5, 7, 9, 11, 13, 15] ; 当 N = 3 时， Ys = [1,2, 4,5, 7,8, 10,11, 13,14 ] ; 当 N = 4 时， Ys = [1,2,3, 5,6,7, 9,10,11, 13,14,15] ; 当 N = 5 时， Ys = [1,2,3,4, 6,7,8,9, 11,12,13,14 ] ; 当 N = 6 时， Ys = [1,2,3,4,5, 7,8,9,10,11, 13,14,15] ; 当 N = 7 时， Ys = [1,2,3,4,5,6, 8,9,10,11,12,13, 15] ; 当 N = 8 时， Ys = [1,2,3,4,5,6,7, 9,10,11,12,13,14,15] ; 当 N = 9 时， Ys = [1,2,3,4,5,6,7,8, 10,11,12,13,14,15] ; 当 N = 10 时， Ys = [1,2,3,4,5,6,7,8,9, 11,12,13,14,15] ; 当 N = 11 时， Ys = [1,2,3,4,5,6,7,8,9,10, 12,13,14,15] ; 当 N = 12 时， Ys = [1,2,3,4,5,6,7,8,9,10,11, 13,14,15] ; 当 N = 13 时， Ys = [1,2,3,4,5,6,7,8,9,10,11,12, 14,15] ; 当 N = 14 时， Ys = [1,2,3,4,5,6,7,8,9,10,11,12,13, 15] ; 当 N = 15 时， Ys = [1,2,3,4,5,6,7,8,9,10,11,12,13,14 ] ; 当 N > 15 时， Ys = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].

- repeat

Answer 3

编辑，更正了@CapelliC指出的错误，在N = 0时谓词将成功。

我可以看出你在解决方案中的想法，但在这种情况下，你不需要进行太多的算术运算。我们可以通过从N开始重复向下计数直到列表为空来删除第N个元素。首先，关于样式的一点快速说明：

如果您使用空格、换行和正确的括号位置，您可以帮助读者解析您的代码。在此形式下，您的最后一个子句更易读：

delete_nth([X|L], C, L1):-
    listnum(L, S),
    Num is S+1,
    C>0 -> Y is round(Num/C),
    Y=0 -> delete_nth(L, C, L1)
    ; delete_nth(L, C, [X|L1]).

查看您的代码，我不确定您是否打算写成

。

( C>0 -> ( Y is round(Num/C), 
           Y=0 -> delete_nth(L, C, L1) )
; delete_nth(L, C, [X|L1])
).

或者如果您的意思是

C>0 -> Y is round(Num/C), 
( Y=0 -> delete_nth(L, C, L1)
; delete_nth(L, C, [X|L1])
).

或许你在第二个条件语句之前缺少了一个 ; ？无论如何，我建议采用另一种方法......

这似乎是一个需要辅助谓语的问题！

通常，我们只需要一个简单的关系来提出查询，但必要的计算过程以解决查询并得出答案需要更复杂的关系。这些情况往往是“说起来容易做起来难”的。

我提供的解决方案如下：为了删除每个第n个元素，我们从N开始倒数到1。每次从N减去该值时，我们将一个元素从原始列表移动到我们保留的元素列表中。当我们到达1时，我们丢弃原始列表中的元素，并从N重新开始倒数。如您所见，为了提出问题“删除List中每个N个��素后得到的列表Kept是什么？”，我们仅需要三个变量。但我的答案还需要另一个变量来跟踪从N到1的倒数计数，因为每次我们从List中取出头部时，我们需要问“Count是什么？”一旦我们到达1，我们需要能够记住N的原始值。

因此，我提供的解决方案依赖于一个辅助的4个元素谓词来进行计算，并使用一个3个元素谓词作为“前端”，即用于提出问题的谓词。

delete_nth(List, N, Kept) :-
    N > 0,                                  %% Will fail if N < 0.
    delete_nth(List, N, N, Kept), !.        %% The first N will be our our counter, the second our target value. I cut because there's only one way to generate `Kept` and we don't need alternate solutions.

delete_nth([], _, _, []).                   %% An empty list has nothing to delete.
delete_nth([_|Xs], 1, N, Kept) :-           %% When counter reaches 1, the head is discarded.
    delete_nth(Xs, N, N, Kept).             %% Reset the counter to N.
delete_nth([X|Xs], Counter, N, [X|Kept]) :- %% Keep X if counter is still counting down.
    NextCount is Counter - 1,               %% Decrement the counter.
    delete_nth(Xs, NextCount, N, Kept).     %% Keep deleting elements from Xs...

- Shon

Answer 4

请遵循aBathologist的指导性答案和解释(+1)。我只是发布了自己的解决方案，因为在ditto解决方案中存在问题，如?- delete_nth([a,b,c,d,e,f],0,L)。

delete_nth(L,C,R) :-
    delete_nth(L,C,1,R).

delete_nth([],_,_,[]).
delete_nth([_|T],C,C,T1) :- !, delete_nth(T,C,1,T1).
delete_nth([H|T],N,C,[H|T1]) :- C<N, C1 is C+1, delete_nth(T,N,C1,T1).

产量

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

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

3 ?- delete_nth([a,b,c,d,e,f],0,L).
false.

一个小问题：这段代码是确定性的，而发布的样本显然不是（你必须输入“;”才能在结尾处得到一个false）。去掉切割将产生相同的行为。

一个有趣的 - 在我看来 - 一行变体：

delete_nth(L,C,R) :- findall(E, (nth1(I,L,E),I mod C =\= 0), R).

但必须排除C==0，以避免

ERROR: mod/2: Arithmetic: evaluation error: `zero_divisor'

- CapelliC

---

嗨！你介意解释一下你所说的“在?‐ delete_nth([a,b,c,d,e,f],0,L).这个问题的解决方案中出了什么问题吗？”我运行了查询，但没有看到重复的地方，但我想我可能理解错了你的意思。我是不是放错位置了剪切符？另外，如果你愿意，我想知道从递增计数到递减计数的优势是什么。谢谢！ - Shon

@aBathologist：我指的是你的解决方案在 C == 0 时表现不佳。它保持输入不变，而示例要求一个空列表。关于计数上升/下降：我认为没有任何区别，只是我将解决方案视为“跳过第n个项目”，然后直观地从1开始“项目计数”... - CapelliC

谢谢解释。我完全忽略了0的预期输出！我现在会修复它。我认为你说的从0开始计数更直观，现在我想起来了。 - Shon

Answer 5

另一种方法是跟随@user3598120的初衷，计算不需要的第N个元素，并受到@Sergey Dymchenko的玩耍启发。它使用exclude/3来删除所有1-based索引处是N的倍数的元素。

delete_nth(List, N, Kept) :-
    N > 0, 
    exclude(index_multiple_of(N, List), List, Kept).

index_multiple_of(N, List, Element) :-
    nth1(Index, List, Element),
    0 is Index mod N.

- Shon