Prolog possible removal of elements in a list

Question

I have been asked to try to search for all possible outcomes of, removing any numbers from any single elements from a list.

For example, if I have a list X = [1,2,3]

remove(X, Y)

My result will be:

Y = [2,3]
Y = [1,1,3]
Y = [1,3]
Y = [1,2,2]
Y = [1,2,1]
Y = [1,2]

For this, I have already written 2 solutions, but I don't really know what is the cons of my solutions. My professor keeps telling me that there is a better way of doing this.

My First approach:

test(S1, S2):-
    length(S1, L),
    M is L -1,
    between(0, M, N),
    remove(S1, S2, N).
remove([H|T], [H2|T2], Heap):-
    (
        Heap>0->
        H2 = H,
        remove(T, T2, Heap-1);
        between(1, H, N),
        H2 is H - N,
        T2 = T
    ).

My Second Approach:

remove1([H|T], [H|TY]):-
    not(T=[]),
    remove1(T, TY).
remove1([H|T], S2):-
    between(1, H, X),
    HY is H - X,
    (   HY = 0-> S2 = T; S2=[HY|T]).

Both of the approaches are giving the same result, but I do really want to know how I can do it better. Would anyone mind giving me some advice please?

I am having trouble understanding the problem statement. What do you mean by "removing any numbers from any single elements from a list"? Sometimes, you are removing an element from the list (changing the total number of elements), and sometimes you seem to be subtracting from an element (so the total number of elements remains the same). Which one is it? Or both? — , Nov 11 '15 at 14:05
How do you get, for example, `[1, 1, 2]` when removing an element frim `[1, 2, 3]`? — lurker, Nov 11 '15 at 14:12
Sorry for the confusion, actually it is subtracting an element from the list, if the result is 0, it will be discarded. For example, X = [1,2], Y can be [ 1-1, 2], in this case, 1-1 = 0, so that the result is [2]. Second case is [1, 2-1], so that the result is [1,1]. Third case is [1,2-2], again, 2-2 =0, so that the result is [1]. Hope this make sense. — user3390652, Nov 11 '15 at 14:14
@lurker This is actually the next thing I need to do, but I have no idea on how I can do this. — user3390652, Nov 11 '15 at 14:26
This problem has now completely changed. Your original question was how to remove an element, and you were given two answers. Now you changed the question to introduce two additional answers, and the question has become, "Is there a better way to do this?" That completely changes the question and invalidates the answers given. That should have been asked in a new question rather than completely changing this one. — lurker, Nov 16 '15 at 00:31

score 2 · Accepted Answer · answered Nov 11 '15 at 14:06

2

You have to:

select one item (number) from the list
replace selected item with a number which is less than the selected item
alternatively remove entirely the selected item

For example:

remove([N|Tail], [NX|Tail]):-
  succ(N1, N),
  between(1, N1, NX).
remove([_|Tail], Tail).
remove([N|Tail], [N|NTail]):-
  remove(Tail, NTail).

The first clause selects the first item in the list, and replaces that item with a number which is less than the item.

The second clause removes the item from the list (as shown in your examples when you subtract N to the selected item (N) it does not appear in the second list.

The third clause applies recursion, leaving the head item as-is and applies the procedure to the remaining list.

answered Nov 11 '15 at 14:06

gusbro

22,357
35
46

So by "numbers" we actually mean non-negative integers? – Nov 11 '15 at 14:11
How would you comment on the quality my code, for the second one? Your one looks much better. – user3390652 Nov 11 '15 at 14:20
@Boris: I think OP meant non-negative integers – gusbro Nov 11 '15 at 14:20
But there is a problem here. For my code, I wouldn't get a "false" at the end. How would you prevent this happen?? – user3390652 Nov 11 '15 at 14:22
@Boris Yes, I am talking about non-negative integers. – user3390652 Nov 11 '15 at 14:22
@user3390652: From your second code I would remove the `not(T=[])` from the first clause. That clause is the recursive step which I usually put after the base cases of a recursion. The second clause is somewhat similar to my first and second clauses. **I personally** think it's more readable the version which splits clauses as I did. – gusbro Nov 11 '15 at 14:25
@user3390652: false at that point means there are no more solutions. It should not be a problem – gusbro Nov 11 '15 at 14:26
@gusbro Thanks for your help and comment. :) But I've got another problem related to this question actually. I need to remove any numbers from any 2 elements... I have no idea on starting it... Do you have any ideas? e.g. X = [1,2,3], I can remove from 1st/2nd (Y=[1,3]), 1st/3rd (Y=[1,2,2]), 2nd/3rd(Y=[1,1,2] or [1,1]).. I don't know how to start at all.. – user3390652 Nov 11 '15 at 14:35
@user3390652: There are many ways to solve your "extended" problem. An easy one is to add another procedure that is almost exactly the same as this one, but instead of returning the "Tail" it calls this procedure with the Tail and gets a new list. If you later need a program that removes any number from any number of elements then modify the procedure shown here to recursively call itself using Tail to get a new NTail in the 1st and 2nd clauses. – gusbro Nov 11 '15 at 14:47
@gusbro Cheers:) I will try on it. – user3390652 Nov 11 '15 at 22:35
@gusbro sorry There is a mistake in the example of the "extended problem" in the comment. The correct one is as follow, X = [1,2,3], I can remove from 1st/2nd (Y=[1,3]), 1st/3rd (Y=[2,2]), 2nd/3rd(Y=[1,1,2] or [1,1]. From what I understand from your last comment, I tried with adding the following code, `remove([_Tail], NX):- remove(Tail, NX).` but seems like I am not getting the desired result. – user3390652 Nov 12 '15 at 02:35
1

@user3390652: The comments is not the right place to ask further questions (difficult to show code here). For the extended problem, an easy solution is leave `remove` as-is, then create another procedure `remove2` which is almost the same, but in clauses 1 and 2 change `Tail` in the second argument of head with `NTail` and add a call to `remove(Tail, NTail)` as the last line in both clauses, i.e.: `remove2([N|Tail], [NX|NTail]):- succ(N1, N), between(1, N1, NX), remove(Tail, NTail).` and `remove2([_|Tail], NTail):- remove(Tail, NTail).` – gusbro Nov 12 '15 at 13:57
@gusbro I have tried with this but it is just giving some similar things for me. Maybe the description was not good enough... Would you mind coming on to another page and have a look? http://stackoverflow.com/questions/33696780/prolog-search-for-possible-combination-for-subtracting-2-elements-from-a-list – user3390652 Nov 13 '15 at 15:57

score 2 · Answer 2 · answered Nov 11 '15 at 15:12

Here's another solution using append/3. I'm thinking @gusbro's answer is more elegant and/or efficient. But it's an alternative:

reduce(L, R) :-
    append(L1, [X|L2], L),
    (   X1 is X - 1,              % some element varies 1 to X-1
        between(1, X1, Y),
        append(L1, [Y|L2], R)
    ;   append(L1, L2, R)         % or the element is just removed
    ).

Prolog possible removal of elements in a list

2 Answers2

Linked