partitioning a list

59 views
Skip to first unread message

Checco7

unread,
Jun 26, 2018, 7:05:11 PM6/26/18
to swi-p...@googlegroups.com
how can I partition a list into a list?
example sublists who have sum 4:
list [1,3,4,2,2] produces [[1,3], [4], [2,2]]

I tried a lot but I did not succeed.
Thanks if you help me

I would like to take an L1 list, a list of L2 lists. true if:
L1 is a list of number
L2 is a list of list where the sum is a certain number, for example 20, from 0 to i, and the list i + 1 is the remainder.
example:
partition20 ([12, 11, 7,3,18,1,2], [[12,7,1], [18,2], [11,3]])


my test:

 sum([],0).

sum([X],X).

sum([X,Y|Xs],S):-
   sum([Y|Xs],S1),
    S is X + S1.

rest([], [], []).

rest([A|Ra], [A|Rb], Z) :-
   rest(Ra, Rb, Z).

rest([A|Ra], Rb, [A|Z]) :-
   rest(Ra, Rb, Z).
   
partition([], []).

partition([A|Ra], [[A|Rb]|Rest]) :-
   rest(Ra, Rb, Z),
   partition(Z, Rest),
   sum([A|Rb],20).

Barb Knox

unread,
Jun 26, 2018, 7:26:25 PM6/26/18
to SWI-Prolog, Checco7
On 27/06/2018, at 11:05, Checco7 <pefs...@gmail.com> wrote:

how can I partition a list into a list?
example sublists who have sum 4:
list [1,3,4,2,2] produces [[1,3], [4], [2,2]]

I tried a lot but I did not succeed.

If you have tried a lot, then please show us a couple of your attempts.  This will provide a basis for giving you useful help.


Thanks if you help me

And the Evil Eye if we don’t?

-- 
---------------------------
|  BBB                b    \    Barbara at LivingHistory stop co stop uk
|  B  B   aa     rrr  b     |
|  BBB   a  a   r     bbb   |   ,008015L080180,022036,029037
|  B  B  a  a   r     b  b  |   ,047045,L014114L4.
|  BBB    aa a  r     bbb   |
-----------------------------

Volker Wysk

unread,
Jun 27, 2018, 3:21:14 AM6/27/18
to swi-p...@googlegroups.com
Am Dienstag, 26. Juni 2018, 16:05:11 CEST schrieb Checco7:
> how can I partition a list into a list?
> example sublists who have sum 4:
> list [1,3,4,2,2] produces [[1,3], [4], [2,2]]

This doesn't explain, what you have in mind...

Volker

Checco7

unread,
Jun 27, 2018, 2:13:38 PM6/27/18
to swi-p...@googlegroups.com

some help in the right solution?
Message has been deleted

Kuniaki Mukai

unread,
Jun 30, 2018, 11:30:11 AM6/30/18
to Checco7, SWI-Prolog
Hi, 

Did you find a solution for that lovely exercise ?  I hope you did,
but here is my solution based on select/3 just in case, 
though I am not  sure it is a solution to  your problem.

sublist(0, X, X, Y, Y):-!.
sublist(N, X, Y, Z, U):- N>0, select(A, X, X0),
N0 is N-A,
sublist(N0, X0, Y, [A|Z], U).

?- sublist(3, [1,3,2], R).
%@ R = [[2, 1], [3]] .

sublist(_, [], []).
sublist(N, X, [Z|Y]):-sublist(N, X, X0, [], Z),
sublist(N, X0, Y).

?- sublist(4, [1,3,4,2,2], R).
%@ R = [[3, 1], [4], [2, 2]] .

Hope this help,

Kuniaki Mukai

On Jun 28, 2018, at 3:13, Checco7 <pefs...@gmail.com> wrote:

I would like to take an L1 list, a list of L2 lists. true if:
L1 is a list of number
L2 is a list of list where the sum is a certain number, for example 20, from 0 to i, and the list i + 1 is the remainder.
example:
partition20 ([12, 11, 7,3,18,1,2], [[12,7,1], [18,2], [11,3]])


my test:

 sum([],0).

sum([X],X).

sum([X,Y|Xs],S):-
   sum([Y|Xs],S1),
    S is X + S1.

resto([], [], []).

rest([A|Ra], [A|Rb], Z) :-
   rest(Ra, Rb, Z).

rest([A|Ra], Rb, [A|Z]) :-
   rest(Ra, Rb, Z).
   
partition([], []).

partition([A|Ra], [[A|Rb]|Rest]) :-
   rest(Ra, Rb, Z),
   partition(Z, Rest),
   sum([A|Rb],20).




--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

Kuniaki Mukai

unread,
Jun 30, 2018, 10:46:37 PM6/30/18
to Checco7, SWI-Prolog
Hi,

I have changed my codes in the previous post a little bit in order to
keep the ordering for each sublist with that of the original one
by using difference lists, which are ubiquitous in Prolog
programming.

sublist(0, X, X, Y, Y):-!.
sublist(N, X, Y, [A|Z], U):- N>0, select(A, X, X0),
N0 is N-A,
sublist(N0, X0, Y, Z, U).
%
partition_by_weight(_, [], []).
partition_by_weight(N, X, [Z|Y]):-sublist(N, X, X0, Z, []),
partition_by_weight(N, X0, Y).

% ?- partition_by_weight(4, [1,3,4,2,2], R).
%@ R = [[1, 3], [4], [2, 2]] .

If I am helping you too much, I am very sorry. Your problem
was interesting for me too. 

Thanks,

Kuniaki Mukai

On Jun 28, 2018, at 3:16, Checco7 <pefs...@gmail.com> wrote:

Kuniaki Mukai

unread,
Jul 2, 2018, 10:26:19 PM7/2/18
to SWI-Prolog, Checco7
Hi,

I noticed that my previous codes searches unnecessary “solutions”.

Here is a revised version in that point, though I only hope so
without confidence. Now I am a person who would like to know
an  "official" answer to the problem if any.

% ?- partition_by_weight(4, [1,3,4,2,2], R).
%@ R = [[1, 3], [4], [2, 2]] ;
%@ false.

% ?- partition_by_weight(5, [1,3,4,2,3,2], R).
%@ R = [[1, 4], [3, 2], [3, 2]] ;
%@ R = [[1, 4], [3, 2], [2, 3]] ;
%@ false.

partition_by_weight(_, [], []).
partition_by_weight(N, X, [Z|Y]):- sublist(N, X, Z, X0),
partition_by_weight(N, X0, Y).

% ?- sublist(4, [1,3,4,2,2], R, X).
sublist(N, [A|X], [A|Z], X0):- N0 is N-A,
sublist_aux(N0, X, X0, Z, []).

%
sublist_aux(0, X, X, Y, Y):-!.
sublist_aux(N, X, Y, [A|Z], U):- N>0,
select(A, X, X0),
N0 is N-A,
sublist_aux(N0, X0, Y, Z, U).

Kuniaki Mukai
Reply all
Reply to author
Forward
0 new messages