# partitioning a list

59 views

### Checco7

Jun 26, 2018, 7:05:11 PM6/26/18
how can I partition a list into a list?
example sublists who have sum 4:
list [1,3,4,2,2] produces [[1,3], , [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

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], , [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

Jun 27, 2018, 3:21:14 AM6/27/18
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], , [2,2]]

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

Volker

### Checco7

Jun 27, 2018, 2:13:38 PM6/27/18

some help in the right solution?
Message has been deleted

### Kuniaki Mukai

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

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], , [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.

### Kuniaki Mukai

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], , [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

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], , [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