Prolog program that deletes every n-th element from a list

Question

Could you help me solve the following?

Write a ternary predicate delete_nth that deletes every n-th element from a list.

Sample runs:

?‐ 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

I tried this:

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])
   ).

Answer 1

My slightly extravagant variant:

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
    ).

Answer 2

Let's use clpfd! For the sake of versatility and tons of other good reasons:

:- use_module(library(clpfd)).

We define delete_nth/3 based on if_/3 and (#>=)/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).

Sample query:

?- 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]                 % succeeds deterministically

Ok, how about something a little more general?

?- 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 in 16..sup, Ys = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15].

Answer 3

Edited, correcting the mistake pointed out by @CapelliC, where predicate would succeed on N = 0.

I can see where you're headed with your solution, but you needn't bother with so much arithmetic in this case. We can delete the Nth element by counting down from N repeatedly until the list is empty. First, a quick note about style:

If you use spaces, line breaks, and proper placement of parenthesis you can help your readers parse your code. Your last clause is much more readable in this form:

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]).

Viewing your code now, I'm not sure whether you meant to write

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

or if you meant

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

or perhaps you're missing a ; before the second conditional? In any case, I suggest another approach...

This looks like a job for auxiliary predicates!

Often, we only need a simple relationship in order to pose a query, but the computational process necessary to resolve the query and arrive at an answer calls for a more complex relation. These are cases where it is "easier said than done".

My solution to this problem works as follows: In order to delete every nth element, we start at N and count down to 1. Each time we decrement the value from N, we move an element from the original list to the list of elements we're keeping. When we arrive at 1, we discard the element from our original list, and start counting down from N again. As you can see, in order to ask the question "What is the list Kept resulting from dropping every Nth element of List?" we only need three variables. But my answer the question, also requires another variable to track the count-down from N to 1, because each time we take the head off of List, we need to ask "What is the Count?" and once we've reached 1, we need to be able to remember the original value of N.

Thus, the solution I offer relies on an auxiliary, 4-place predicate to do the computation, with a 3-place predicate as the "front end", i.e., as the predicate used for posing the question.

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...

Answer 4

Please follow aBathologist instructive answer and explanation (+1). I just post my own bet at solution since there is a problem in ditto solution for ?‐ 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).

yields

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.

A minor (?) problem: this code is deterministic, while the samples posted apparently are not (you have to input ';' to get a false at end). Removing the cut will yield the same behaviour.

An interesting - imho - one liner variant:

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

but the C==0 must be ruled out, to avoid

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

Answer 5

Yet another approach, following up on @user3598120 initial impulse to calculate the undesirable Nth elements away and inspired by @Sergey Dymchenko playfulness. It uses exclude/3 to remove all elements at a 1-based index that is multiple of 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.