# Permutations - Stuck in a infinite loop

I have done an algorithm wich gets the most time-efficent list from the permutated lists of a certain list.
When i try to run it for a small list (with 2 elements) it works, however, when i try with a bigger list, it get stuck after trying with a small portion of the permutated lists.
I tried tracing the algorithm to see what was wrong and after doing the first list it got stuck on a infinite loop, does somebody know what i am doing wrong?

My code:

``````%a armazensEntregas
armazens_entregas(L):- findall(K,entrega(_,_,_,K,_,_),L).

:-dynamic custo_min/2.

%c calcula_tempo
calcula_tempo(LC,Final):-
bateria_camiao(LC,CarM,TempR),
peso_camiao(3,PesoC),
tempo_recarga(LC,CarM,TempR,RecargaC,PesoC),
tempo_extra(LC,ExtraC),
tempo_entregas(LC,TempoE),
tempo(LC,Custo,PesoC),
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final).

%custo
tempo([_],0,_).
tempo([C1,C2|LC],Custo,PesoC):-
entregas_peso(C1,LE),
peso_entregas(LE,PesoE),
PesoC1 is PesoC - PesoE,
tempo([C2|LC],Custo1,PesoC1),
peso_camiao(C1,PesoB),
Tempo1 is (PesoC1*Tempo)/PesoB,
Custo is Custo1+Tempo1.

%d bateria_camiao (assumindo que o máximo de carga em % é 80%)

%e peso do camiao (assumindo que possui carga máxima)
peso_camiao(C1,PesoC):- dadosCam_t_e_ta(Nome,C1,_,_,_,_),carateristicasCam(Nome,Tara,CapC,_,_,_), PesoC is Tara + CapC.

%e tempo_extra
tempo_extra([_],0).
tempo_extra([C1,C2|LC],ExtraC):-
tempo_extra([C2|LC],ExtraC1),
ExtraC is ExtraC1 + Extra.

%f tempo_recarga
tempo_recarga([_],_,_,0,_).
tempo_recarga([C1,C2|LC],CarM,TempR,RecargaC,PesoC):-
entregas_peso(C1,LE),
peso_entregas(LE,PesoE),
PesoC1 is PesoC - PesoE,
tempo_recarga([C2|LC],CarM,TempR,RecargaC1,PesoC1),
peso_camiao(C1,PesoB),
Energia1 is (PesoC1*Energia)/PesoB,
((CarM - Energia1 < 20, RecargaC is RecargaC1 + ((80 - (CarM - Energia1))*TempR)/60);RecargaC is RecargaC1 + 0).

%g entregas_peso
entregas_peso(C1,LE):- findall(M,entrega(_,_,M,C1,_,_),LE).

%g tempo_entregas
tempo_entregas([],0).
tempo_entregas([HC|LC],TempoE):-
tempo_entregas(LC,TempoE1),
buscar_entregas(HC,LI),
entregas_tempo(LI,TempoT),
TempoE is TempoE1 + TempoT.

%k buscar_entregas
buscar_entregas(HC,LI):-findall(Id,entrega(Id,_,_,HC,_,_),LI).

%j entregas_tempo
entregas_tempo([],0).
entregas_tempo([HI|LI],TempoT):-
entregas_tempo(LI,TempoT1),
entrega(HI,_,_,_,T,TS),
TempoT is TempoT1 + (T + TS).

%h peso_entregas
peso_entregas([],0).
peso_entregas([HC1|LC1],PesoE):-
peso_entregas(LC1,PesoE1), PesoE is PesoE1 + HC1.

%i somar_tudo
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final):- Final is (RecargaC + ExtraC + TempoE + Custo).

%d seq_custo_min

seq_custo_min(LC,Final):-(run;true),custo_min(LC,Final).

run:-
retractall(custo_min(_,_)),
assertz(custo_min(_,100000)),
armazens_entregas(LC),
permutation(LC,LCPerm),
calcula_tempo(LCPerm1,Final),
atualiza(LCPerm1,Final),
fail.

atualiza(LCPerm1,Final):-
custo_min(_,FinalMin),
((Final<FinalMin,!,retract(custo_min(_,_)),assertz(custo_min(LCPerm1,Final)),
write(Final),nl)
;true).

``````

Is your problem related to this description ?

For a give list L, calculate max of the set { f(p) | p is a permutation of L }
where f is a certain numeric function on permutation of L.

It was hard for me to guess from your codes without hint for the problem description.

After looking again , i realised that in some of the methods i was seaching for a value incorrectly.
This corrected some of the problem as now a i can use a bigger list and obtain a result.
However for 6 elements it gets stuck.
I send here the data i use for running and also the updated code.
Anything you want me to clarify, tell me.

``````%idArmazem(<local>,<codigo>)
idArmazem('Arouca',1).
idArmazem('Espinho',2).
idArmazem('Gondomar',3).
idArmazem('Maia',4).
idArmazem('Matosinhos',5).
idArmazem('Oliveira de Azemeis',6).
idArmazem('Paredes',7).
idArmazem('Porto',8).
idArmazem('Povoa de Varzim',9).
idArmazem('Santa Maria da Feira',10).
idArmazem('Santo Tirso',11).
idArmazem('Trofa',13).
idArmazem('Vale de Cambra',14).
idArmazem('Valongo',15).
idArmazem('Vila do Conde',16).
idArmazem('Vila Nova de Gaia',17).

carateristicasCam(eTruck01,7500,4300,80,100,60).

% entrega(<idEntrega>,<data>,<massaEntrega>,<armazemEntrega>,<tempoColoc>,<tempoRet>).
entrega(4439, 20221205, 200, 1, 8, 10).
entrega(4438, 20221205, 150, 9, 7, 9).
entrega(4445, 20221205, 100, 3, 5, 7).
entrega(4443, 20221205, 120, 8, 6, 8).
entrega(4449, 20221205, 300, 11, 15, 20).
%entrega(4398, 20221205, 310, 17, 16, 20).
%entrega(4432, 20221205, 270, 14, 14, 18).
%entrega(4437, 20221205, 180, 12, 9, 11).
%entrega(4451, 20221205, 220, 6, 9, 12).
%entrega(4452, 20221205, 390, 13, 21, 26).
%entrega(4444, 20221205, 380, 2, 20, 25).
%entrega(4455, 20221205, 280, 7, 14, 19).
%entrega(4399, 20221205, 260, 15, 13, 18).
%entrega(4454, 20221205, 350, 10, 18, 22).
%entrega(4446, 20221205, 260, 4, 14, 17).
%entrega(4456, 20221205, 330, 16, 17, 21).

%a armazensEntregas
armazens_entregas(L):- findall(K,entrega(_,_,_,K,_,_),L).

%c nome_camiao

:-dynamic custo_min/2.

%c calcula_tempo
calcula_tempo(LC,Final):-
nome_camiao(LC,Nome),
bateria_camiao(Nome,CarM,TempR),
nome_camiao(LC,Nome),
peso_camiao(Nome,PesoC),
tempo_recarga(LC,CarM,TempR,RecargaC,PesoC,Nome),
tempo_extra(LC,ExtraC),
tempo_entregas(LC,TempoE),
tempo(LC,Custo,PesoC,Nome),
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final).

%d custo
tempo([_],0,_,_).
tempo([C1,C2|LC],Custo,PesoC,Nome):-
entregas_peso(C1,LE),
peso_entregas(LE,PesoE),
PesoC1 is PesoC - PesoE,
tempo([C2|LC],Custo1,PesoC1,Nome),
peso_camiao(Nome,PesoB),
Tempo1 is (PesoC1*Tempo)/PesoB,
Custo is Custo1+Tempo1.

%e bateria_camiao (assumindo que o maximo de carga em e 80%)
bateria_camiao(Nome,CarM1,TempR):- carateristicasCam(Nome,_,_,CarM,_,TempR),CarM1 is CarM*(0.8).

%f peso do camiao (assumindo que possui carga maxima)
peso_camiao(Nome,PesoC):- carateristicasCam(Nome,Tara,CapC,_,_,_), PesoC is Tara + CapC.

%g tempo_extra
tempo_extra([_],0).
tempo_extra([C1,C2|LC],ExtraC):-
tempo_extra([C2|LC],ExtraC1),
ExtraC is ExtraC1 + Extra.

%h tempo_recarga
tempo_recarga([_],_,_,0,_,_).
tempo_recarga([C1,C2|LC],CarM,TempR,RecargaC,PesoC,Nome):-
entregas_peso(C1,LE),
peso_entregas(LE,PesoE),
PesoC1 is PesoC - PesoE,
tempo_recarga([C2|LC],CarM,TempR,RecargaC1,PesoC1,Nome),
peso_camiao(Nome,PesoB),
Energia1 is (PesoC1*Energia)/PesoB,
((CarM - Energia1 < 20, RecargaC is RecargaC1 + ((80 - (CarM - Energia1))*TempR)/60);RecargaC is RecargaC1 + 0).

%i entregas_peso
entregas_peso(C1,LE):- findall(M,entrega(_,_,M,C1,_,_),LE).

%j tempo_entregas
tempo_entregas([],0).
tempo_entregas([HC|LC],TempoE):-
tempo_entregas(LC,TempoE1),
buscar_entregas(HC,LI),
entregas_tempo(LI,TempoT),
TempoE is TempoE1 + TempoT.

%k buscar_entregas
buscar_entregas(HC,LI):-findall(Id,entrega(Id,_,_,HC,_,_),LI).

%l entregas_tempo
entregas_tempo([],0).
entregas_tempo([HI|LI],TempoT):-
entregas_tempo(LI,TempoT1),
entrega(HI,_,_,_,T,TS),
TempoT is TempoT1 + (T + TS).

%m peso_entregas
peso_entregas([],0).
peso_entregas([HC1|LC1],PesoE):-
peso_entregas(LC1,PesoE1), PesoE is PesoE1 + HC1.

%n somar_tudo
somar_tudo(RecargaC,ExtraC,TempoE,Custo,Final):- Final is (RecargaC + ExtraC + TempoE + Custo).

%o seq_custo_min

seq_custo_min(LC,Final):-get_time(Ti),(run;true),custo_min(LC,Final),get_time(Tf),TSol is Tf-Ti,write("Tempo final:"),write(TSol), nl.

run:-
retractall(custo_min(_,_)),
assertz(custo_min(_,100000)),
armazens_entregas(LC),
permutation(LC,LCPerm),
calcula_tempo(LCPerm1,Final),
atualiza(LCPerm1,Final),
fail.

atualiza(LCPerm1,Final):-
custo_min(_,FinalMin),
((Final<FinalMin,!,retract(custo_min(_,_)),assertz(custo_min(LCPerm1,Final)),
write(Final),nl)
;true).

% o write(Custo),nl so para ver a atualizacao do menor custo

``````

Cheers.

It runs in a couple of seconds, if you replace the `permutation` line with `LC = LCPerm`

Do you really need that permutation line? Or could the permutation be moved to after the minimum value has been calculated?

Looks like you could use e.g. `min_ratchet` at clpBNR Guide to improve performance.

I use the permutation so i can calculate the minimum time comparing all the permutated lists, so probably not.
Is there a way to make permutations without consuming so much time?

If all permutations need to be generated, N=11 seems the maximum,
where N is the number of elements of the given list for permutations.
As you know, it grows rapidly huge, more worse than the notorius exponential 2^N.

``````% ?- N = 20, forall(between(1, N, J), (factorial(J, FJ), format("~w! = ~w\n", [J, FJ]))).
%@ 1! = 1
%@ 2! = 2
%@ 3! = 6
%@ 4! = 24
%@ 5! = 120
%@ 6! = 720
%@ 7! = 5040
%@ 8! = 40320
%@ 9! = 362880
%@ 10! = 3628800
%@ 11! = 39916800
%@ 12! = 479001600
%@ 13! = 6227020800
%@ 14! = 87178291200
%@ 15! = 1307674368000
%@ 16! = 20922789888000
%@ 17! = 355687428096000
%@ 18! = 6402373705728000
%@ 19! = 121645100408832000
%@ 20! = 2432902008176640000
%@ N = 20.
``````

Right, but my algorithm for only 6! takes an absurd time(i waited hours and it didnt even worked), i tried to calculate the exponential function and if it was correct my algorithm for 6! would take one hour and 30 minutes.
What i inted to know is if iam using incorrectly something that raises my the algorithm’s time drastically, because i believe it should be able to find the best solution in much less time.
I

The number of permutations increases very fast. The only way I know of limiting this is to set up “lazy” constraints that prune the backtracking tree.

``````    maplist(constrain(Puzzle), Guesses, Results),
constrain_black(Puzzle, Guesses, Results),
puzzle_fill(Puzzle), % generate permutations in Puzzle
``````

where `constrain_from_guess/3` uses dif/2 to set up inequalities, which greatly reduce the permutation tree. (This code also has some constraints after `puzzle_fill/1`; not all constraints can be set up “lazily”)

In your case, where you’re trying to minimize, you might need to use something like nb_setval/2 et al to keep track of the minimum and remove permutations as soon as their vaue is too high.
Another possibility is to use tabling with minimum.