Create a list of empty lists 1

[aa676]

Hello i need to create a list of empty lists eg [ [], [] , [] , []] but the problem is, i need the exact number of empty lists provided from the input.. for example if i give createEptyLists(4,X). it should return X= [ [], [] , [] , [] ].

how can i implement this " for i=<InputNumberOfLists" ?

 

[aa676]

ok found how to do that but now i have an other problem here is my code:

binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
createBins([[]],NumBins,Bins),
addIn(ObjectList,Capacity,Bins,AnswerListOfLists).



createBins(L1,N,L2):-createBins(L1,N,L2,N).

createBins([],_,[],_).
createBins([_|Xs],N,Ys,0) :- createBins(Xs,N,Ys,N).
createBins([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, createBins([X|Xs],N,Ys,K1).



addIn(RemNum,Cap,Bins,Ext):-
getFirst(X,RemNum),
member( M , Bins),
sum( M, Y),
C is Y + X,
C=<Cap,append([X], M, T),insert( M, T, Bins, Ext);
[_|Z]=RemNum,
addIn(Z,Cap,Bins,Ext).



getFirst(X,Y):- [X|_] = Y.

sum([],0).
sum([H|T],TotalSum):-
sum(T,Sum1),
TotalSum is H+Sum1.

insert(Old,New,[Old|Rest],[New|Rest]).
insert(Old,New,[X|R1],[X|R2]):- insert(Old,New,R1,R2).

it returns:

Answer = [[7], [], []] ;
Answer = [[], [7], []] ;
Answer = [[], [], [7]] ;
Answer = [[7], [], []] ;
Answer = [[], [7], []] ;
Answer = [[], [], [7]] ;
Answer = [[7], [], []] ;
Answer = [[], [7], []] ;
Answer = [[], [], [7]] ;
Answer = [[3], [], []] ;
Answer = [[], [3], []] ;
Answer = [[], [], [3]] ;
...

until the end of all the elements.. but i want it to return:

Answer = [[2,4,6],[4,5,3],[5,7]]

its a typical simple bin packing problem, any ideas?

 

[aa676]

ok fixed that but now a different problem here is the code:

binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
createBins([[]],NumBins,Bins),
addIn(ObjectList,Capacity,Bins,AnswerListOfLists).


createBins(L1,N,L2):-createBins(L1,N,L2,N).

createBins([],_,[],_).
createBins([_|Xs],N,Ys,0) :- createBins(Xs,N,Ys,N).
createBins([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, createBins([X|Xs],N,Ys,K1).



addIn([HeadObjectList|TailObjectList],Cap,Bins,Answ):-
%getFirst(X,ObjectList),
member( M , Bins),
sum( M, Y),
C is Y + HeadObjectList,
(
C=<Cap,append([HeadObjectList], M, T),insert( M, T, Bins, Answ2), 
		addIn(TailObjectList,Cap,Answ2,Answ);
%[_|Z]=TailObjectList,
addIn([HeadObjectList|TailObjectList],Cap,Bins,Answ)
).



getFirst(X,Y):- [X|_] = Y.

sum([],0).
sum([H|T],TotalSum):-
sum(T,Sum1),
TotalSum is H+Sum1.

insert(Old,New,[Old|Rest],[New|Rest]).
insert(Old,New,[X|R1],[X|R2]):- insert(Old,New,R1,R2).

my problem is how can i get it to pass to the next bin and not enter into a finite loop when it reaches Answer=[[3,7],[],[]]. and the next number to enter is 5?

 

[joel76]

Hello

This line is wrong :

addIn([HeadObjectList|TailObjectList],Cap,Bins,Answ):-
   %getFirst(X,ObjectList),
   member( M , Bins),
   sum( M, Y),
   C is Y + HeadObjectList,
   (
      C=<Cap,append([HeadObjectList], M, T),insert( M, T, Bins, Answ2),
      addIn(TailObjectList,Cap,Answ2,Answ);
      %[_|Z]=TailObjectList,
 ===>     addIn([HeadObjectList|TailObjectList],Cap,Bins,Answ)
).

You call exactly the same thing, with no change, that's why you loop.

You should consider 3 cases : C < Cap, you keep on, C = Cap, a sublist is full and C > Cap, just fail.

I think you shouldn't give the number of sublists you want.
When a sublist is full, you add it in the answer list and you keep on with a new sublist. (just what I Think !).

 

[joel76]

I study deeper your programm (bad english ?), and it works with two change :
when C =< Cap fails, do nothing, backtrack works well.
You forgot the case when all numbers are used, what must you do ?

 

[aa676]

your answer confused me a little bit, so one change is to make C=< Cap do nothing when it fails? or just leave it as it is? and the second change is to do something when all numbers are used?

this is what i tried to do but now 2 things happen, when it reaches the last bin and the next number doesn't fit, it doesn't check if it fits in previous bins, and the other thing is that i doesn't carry the rest of the bins along it just tries the next without considering the previous.

binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
createBins([[0]],NumBins,Bins),
addIn(ObjectList,Capacity,Bins,AnswerListOfLists).


createBins(L1,N,L2):-createBins(L1,N,L2,N).

createBins([],_,[],_).
createBins([_|Xs],N,Ys,0) :- createBins(Xs,N,Ys,N).
createBins([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, createBins([X|Xs],N,Ys,K1).

addIn([],_,_,_):- !.

addIn([HeadObjectList|TailObjectList],Cap,[BinsH|BinsT],Answ):-
member( M , [BinsH|BinsT]),
sum( M, Y),
C is Y + HeadObjectList,
(
C=<Cap,append([HeadObjectList], M, T),insert( M, T, [BinsH|BinsT], Answ2), 
		
addIn(TailObjectList,Cap,Answ2,Answ);

addIn([HeadObjectList|TailObjectList],Cap,[BinsT],Answ)


).



getFirst(X,Y):- [X|_] = Y.

sum([],0).
sum([H|T],TotalSum):-
sum(T,Sum1),
TotalSum is H+Sum1.

insert(Old,New,[Old|Rest],[New|Rest]).
insert(Old,New,[X|R1],[X|R2]):- insert(Old,New,R1,R2).

 

[joel76]

I'm sorry.

addIn([],_,_,_):- !.

This is false, you must unify Answ and Bins :

addIn([],_Cap,Answ,Answ).

For the second clause :

addIn([HeadObjectList|TailObjectList],Cap,Bins,Answ):-
	member(M , Bins),
	sumlist(M, Y),
	C is Y + HeadObjectList,
	( C=<Cap,append([HeadObjectList], M, T),
	  insert( M, T, Bins, Answ2),
	  addIn(TailObjectList,Cap,Answ2,Answ)).

 

[aa676]

thank you joel very much, you've been really helpful thanks. This works fine,but i still need to figure out one thing: when a number comes that doesn't fit in any bin the program fails, if that happens i need it go back, re-arrange the object list and start again from the start.

here is what the trace returns at that point

...
 202   10  Redo: member([4,6,0],[[3,7,0],[4,5,0],[4,6,0]]) ? 
    202   10  Fail: member(_5618,[[3,7,0],[4,5,0],[4,6,0]]) ? 
    201    9  Fail: addIn([5,2],12,[[3,7,0],[4,5,0],[4,6,0]],_3392) ? 
    198    9  Redo: insert([6,0],[4,6,0],[[3,7,0],[4,5,0],[6,0]],[[3,7,0],[4,5,0],[4,6,0]]) ? 
    199   10  Redo: insert([6,0],[4,6,0],[[4,5,0],[6,0]],[[4,5,0],[4,6,0]]) ? 
    200   11  Redo: insert([6,0],[4,6,0],[[6,0]],[[4,6,0]]) ? 
    201   12  Call: insert([6,0],[4,6,0],[],_5560) ? 
    201   12  Fail: insert([6,0],[4,6,0],[],_5560) ? 
    200   11  Fail: insert([6,0],[4,6,0],[[6,0]],_5532) ? 
    199   10  Fail: insert([6,0],[4,6,0],[[4,5,0],[6,0]],_5504) ? 
    198    9  Fail: insert([6,0],[4,6,0],[[3,7,0],[4,5,0],[6,0]],_5505) ? 
    189    9  Redo: member([6,0],[[3,7,0],[4,5,0],[6,0]]) ? 
    189    9  Fail: member(_5262,[[3,7,0],[4,5,0],[6,0]]) ? 
    188    8  Fail: addIn([4,5,2],12,[[3,7,0],[4,5,0],[6,0]],_3392) ? 
    185    8  Redo: insert([0],[6,0],[[3,7,0],[4,5,0],[0]],[[3,7,0],[4,5,0],[6,0]]) ? 
    186    9  Redo: insert([0],[6,0],[[4,5,0],[0]],[[4,5,0],[6,0]]) ?
...

.

i think i need something here:

addIn([],_Cap,Answ,Answ).

if that is true, stop, if not re-arrange objectlist and call binpack again with the re-arranged list.

 

[joel76]

Yes you'are right.
You have to test what happen when there is a single number in the list.
I have a solution but I haven't yet test all possibilities, so I leave you find it !

 

[aa676]

ok done it, it works perfect. but i need one more last advice
here is the code:

binpack(_,_,[],AnswerListOfLists):- !.
binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
createBins([[]],NumBins,Bins),

(addIn(ObjectList,Capacity,Bins,AnswerListOfLists);
 perm(ObjectLisT,RandomList),
 binpack(NumBins,Capacity,RandomList,AnswerListOfLists)).



createBins(L1,N,L2):-createBins(L1,N,L2,N).

createBins([],_,[],_).
createBins([_|Xs],N,Ys,0) :- createBins(Xs,N,Ys,N).
createBins([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, createBins([X|Xs],N,Ys,K1).

addIn([],_Cap,Answ,Answ).
addIn([HeadObjectList|TailObjectList],Cap,[BinsH|BinsT],Answ):-
member( M , [BinsH|BinsT]),
sum( M, Y),
C is Y + HeadObjectList,
(
C=<Cap,append([HeadObjectList], M, T),
insert( M, T, [BinsH|BinsT], Answ2), 		
addIn(TailObjectList,Cap,Answ2,Answ)

).

sum([],0).
sum([H|T],TotalSum):-
sum(T,Sum1),
TotalSum is H+Sum1.

insert(Old,New,[Old|Rest],[New|Rest]).
insert(Old,New,[X|R1],[X|R2]):- insert(Old,New,R1,R2).

when i call it a like this:

binpack(3,12,[7, 3, 5, 4, 6, 4, 5, 2], Answer).

it returns

Answer = [[5,7],[5,4,3],[2,4,6]] ? ;

Answer = [[5,7],[5,4,3],[2,6,4]] ? ;

Answer = [[5,7],[4,5,3],[2,4,6]] ? ;

Answer = [[5,7],[4,5,3],[2,6,4]] ? ;
...

that is all the possible answers and is what i wanted.
but if i give it something like that:

binpack(3,11,[8,2,4,6,1,8,4],Answer).

it returns:

uncaught exception: error(existence_error(procedure,perm/2),binpack/4)

because obviously it is not possible to pack these numbers into bins. How can i make it return 'no' instead of the error message?

 

[joel76]

You have this error message because you haven't code perm/2.

I think I gave you a bad answer at the question

"i think i need something here:

addIn([],_Cap,Answ,Answ).

if that is true, stop, if not re-arrange objectlist and call binpack again with the re-arranged list."

I said you're right for "i think i need something here:" not for "if not re-arrange objectlist and call binpack again with the re-arranged list."
Backtrack do the job, if it's not possible and you want "no", you have nothing to do :

binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
createBins([[]],NumBins,Bins),
addIn(ObjectList,Capacity,Bins,AnswerListOfLists).

If you want to get a list with the rest of the numbers when it's not possible to pack them you must code the case.

 

[aa676]

can't really figure out where to make it return no, i tried all possible ways of adding fail or !.
here is the final code

binpack(_,_,[],AnswerListOfLists):- !.                      %if no input is provided exit

%Predicate binpack/4 which operates in mode (+,+,+,-)
binpack(NumBins,Capacity,ObjectList,AnswerListOfLists):-
                         createBins([[]],NumBins,Bins),                              %create a list with a NumBins number of empty lists resembling the bins

                          addIn(ObjectList,Capacity,Bins,AnswerListOfLists);         %add all elements of the ObjectList into the empty bins
                          perm(ObjectLisT,RandomList),                               %if you fail, re-arrange the object list
                          binpack(NumBins,Capacity,RandomList,AnswerListOfLists).    %and start packing the bins again with the re-arranged list


%dublicate the elements of a list a given number of times
% createBins(L1,N,L2) :- L2 is obtained from L1 by duplicating all elements
%    N times.
%    (list,integer,list) (?,+,?)
createBins(L1,N,L2):-createBins(L1,N,L2,N). 
  
% createBins(L1,N,L2,K) :- L2 is obtained from L1 by duplicating its leading
%    element K times, all other elements N times.
%    (list,integer,list,integer) (?,+,?,+)                   
createBins([],_,[],_).                                      
createBins([_|Xs],N,Ys,0) :- createBins(Xs,N,Ys,N).         
createBins([X|Xs],N,[X|Ys],K) :- K > 0, K1 is K - 1, createBins([X|Xs],N,Ys,K1).


addIn([],_Cap,Answ,Answ).            %If the object list is empty, return the answer    

%add in function adds elements into existing bins                                                    
addIn([HeadObjectList|TailObjectList],Cap,[BinsH|BinsT],Answ):-
                                      member( M , [BinsH|BinsT]),                   %return all the elements currently in bins
                                      sum( M, Y),                                   %calculate the current capacity of each bin
                                      C is Y + HeadObjectList,                      %calculate the provisional capacity after adding a number
                                      (C=<Cap,append([HeadObjectList], M, T),       %if provisional capacity is below the allowed capacity
                                      insert( M, T, [BinsH|BinsT], Answ2), 	    %insert the number into the respective bin	
                                      addIn(TailObjectList,Cap,Answ2,Answ)).        %call addIn again for the rest of the object list


%getFirst predicate returns the first element of a list
getFirst(X,Y):- [X|_] = Y.

%sum function returns the sum of the elements of a list
sum([],0).
sum([H|T],TotalSum):-
                   sum(T,Sum1),
                   TotalSum is H+Sum1.

%insert function replaces the current status of the list of bins with the 
%the status after a number has been inserted
insert(Old,New,[Old|Rest],[New|Rest]).
insert(Old,New,[X|R1],[X|R2]):- insert(Old,New,R1,R2).

when i trace it i reckon that the problem is in perm(ObjectLisT,RandomList), but how can i make it return no?

 

[joel76]

You don't need this part of code

        ;
	%add all elements of the ObjectList into the empty bins
	perm(ObjectList,RandomList),
	%if you fail, re-arrange the object list
	binpack(NumBins,Capacity,RandomList,AnswerListOfLists).
	%and start packing the bins again with the re-arranged list

When addIn(ObjectList,Capacity,Bins,AnswerListOfLists) fails, backtrack do the job.