Recursivity
Greetings.
I am working on a demand wheres i need to find all the possible combinations of number contained in a string, its works very well, but when the total numbers is increased bigger, the time to execute the code is increased exponentially. Theres a beter way to find combinations then recursively?
string data:
^x(1,1)="211405;211764;211841;211848;211851;212012;212483;212519;212572;212609;212962;213016;213020;213025;213076;213763;214543;216742;216766;217561;217564;217568;217588;219382;219385;219527;219703;219705;219888;219895;220181;220261;220273;220299;220485;220547;220587;220629;220649;220687;220692;220725;220732;220776;220802;220879;220994;221014;221050;221121;221321;221352;221353;221364;221365;221369;221383;221406;221469;221476;221477;221481;221488;221522;221525;221535;221536;221553;221560;221561;221622;221626;221662;221664;221668;221670;221696;221708;221711;221728;221730;221731;221735;221754;221758;221759;221774;221812;221817;221818;221830;221836;221858;221863;221898;221903;221905;221910;221911;221915;221921;221924;221927;221931;221935;221946;221952;221953;221956;221981;221982;221983;222002;222075;222076;222084;222085;222119;222125;222126;222128;222137;222149;222168;222191;222202;222207;222211;222220;222222;222253;222254;222277;222280;222309;222315;222319"
The code is in theend of post
Thx for the interrest and sorry about my bad english.
GCARPVSC102RG ; ALP 10/2024 - GCARPVSC102RG - REGRAS
;
#include %CSUTICSP
;
; TODO: Na rotina CCPVSC103 label 1200, ao excluir as sugestões pela opção customizada de lotes, da a mensagem
; de sucesso para cada sugestão excluída, controlar pelo gatilho já existente e mtemps para dar a mensagem
; uma única vez
; ValidarSugestaoFaturamento
; (ALP - 30/10/2024)
ReordenarGeracaoSugestao(codEmpresa,codTerminal) ;
$$$VAR
new codTransacao,dataHoraUltAlt,pvpdItemGrade,saldoEstoque,saldoSugerir,sc
new codItem,saldoEstoqueDisponivel,saldoEstoqueRegra,tabEstoqueDisponivel
new chave1,chave2,chave3,chave4,chave5,chave6,chave7,chave8,cstno,esatab1
new codNatureza,codPedido,codProduto,codReduzido,codTipoNota,i,tabPedido
new piece,pvpd,pvpdi,recursividade,tabCombinacaoSuficiente,tabPedidoOriginal
;
kill tabEstoqueDisponivel,tabPedido,tabCombinacaoSuficiente,tabPedidoOriginal
;
set (chave1,chave2,chave3,chave4,chave5,chave6,chave7,chave8,codPedido,codItem)=""
for set chave1=$order(^mtempT.CCPVSC101(codTerminal,chave1)) quit:chave1="" do
. for set chave2=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2)) quit:chave2="" do
. . for set chave3=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3)) quit:chave3="" do
. . . for set chave4=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4)) quit:chave4="" do
. . . . for set chave5=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5)) quit:chave5="" do
. . . . . for set chave6=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5,chave6)) quit:chave6="" do
. . . . . . for set chave7=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5,chave6,chave7)) quit:chave7="" do
. . . . . . . for set chave8=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5,chave6,chave7,chave8)) quit:chave8="" do
. . . . . . . . for set codPedido=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5,chave6,chave7,chave8,codPedido)) quit:codPedido="" do
. . . . . . . . . for set codItem=$order(^mtempT.CCPVSC101(codTerminal,chave1,chave2,chave3,chave4,chave5,chave6,chave7,chave8,codPedido,codItem)) quit:codItem="" do
. . . . . . . . . . ;
. . . . . . . . . . set (codReduzido)=""
. . . . . . . . . . for set codReduzido=$order(^PVPD(codEmpresa,codPedido,codItem,2,codReduzido)) quit:codReduzido="" do
. . . . . . . . . . . ;
. . . . . . . . . . . set sc=$$VerPedido^CCPVRG001(codEmpresa,codPedido,,.pvpd)
. . . . . . . . . . . set sc=$$VerPedido^CCPVRG001(codEmpresa,codPedido,codItem,.pvpdi)
. . . . . . . . . . . set codProduto=$piece(pvpdi,z,1)
. . . . . . . . . . . set codTipoNota=$piece(pvpd,z,8)
. . . . . . . . . . . set dataHoraUltAlt=$piece(pvpd,z,78)
. . . . . . . . . . . ;
. . . . . . . . . . . do 1000^CCFT902(0,codTipoNota,+dataHoraUltAlt,$piece(dataHoraUltAlt,",",2),"cstno")
. . . . . . . . . . . set codTransacao=+$piece(cstno,z,17),esatab1=$get(^ESATAB(codEmpresa,1,codTransacao))
. . . . . . . . . . . ;
. . . . . . . . . . . for i=10:1 set piece=$piece(esatab1,z,i) quit:piece="" if $piece(piece,";",2)="-" do
. . . . . . . . . . . . set codNatureza=$piece(piece,";",1)
. . . . . . . . . . . ;
. . . . . . . . . . . set sc=$$VerSaldoAtual^CCESARG001(codEmpresa,codNatureza,codReduzido,.saldoEstoque)
. . . . . . . . . . . if sc'=1 set saldoEstoque=0
. . . . . . . . . . . set saldoEstoqueDisponivel=saldoEstoque
. . . . . . . . . . . ;
. . . . . . . . . . . ; Atualiza o estoque disponivel descontando as quantidade em pedido, no momento
. . . . . . . . . . . ; não estará considerando esse desconto.
. . . . . . . . . . . ;if saldoEstoqueDisponivel>0 do
. . . . . . . . . . . ;. set sc=$$VerSaldoProduto^CCPVRG001(codEmpresa,codReduzido,.saldoEstoqueRegra,codNatureza,codProduto)
. . . . . . . . . . . ;. if (sc=1)&&(saldoEstoqueRegra>0) set saldoEstoqueDisponivel=saldoEstoqueDisponivel-saldoEstoqueRegra
. . . . . . . . . . . ;
. . . . . . . . . . . if saldoEstoqueDisponivel<0 set saldoEstoqueDisponivel=0
. . . . . . . . . . . ;
. . . . . . . . . . . set sc=$$ObterPedidoItemGrade^CCPVRG001(codEmpresa,codPedido,codItem,codReduzido,.pvpdItemGrade)
. . . . . . . . . . . ;
. . . . . . . . . . . set saldoSugerir=$piece(pvpdItemGrade,z,1)-$piece(pvpdItemGrade,z,2)-$piece(pvpdItemGrade,z,3)
. . . . . . . . . . . ;
. . . . . . . . . . . set tabPedido(codPedido,codItem,codReduzido)=saldoSugerir
. . . . . . . . . . . ;
. . . . . . . . . . . set tabEstoqueDisponivel(codReduzido)=saldoEstoqueDisponivel
;
;
merge tabPedidoOriginal=tabPedido
merge ^g=tabPedidoOriginal
;
set recursividade=0
set sc=$$TESTE2^GCARPVSC102RG(.tabPedido,.tabEstoqueDisponivel,recursividade,.tabCombinacaoSuficiente)
;
;m ^b=tabPedido
m ^c=tabEstoqueDisponivel
m ^d=tabCombinacaoSuficiente
;
kill ^mtempT.CCPVSC101(codTerminal)
;
set seqComb=""
for set seqComb=$order(tabCombinacaoSuficiente(seqComb)) quit:seqComb="" do
. ;
. set sc=$$ConvertStrTab^%CSW1E($piece(tabCombinacaoSuficiente(seqComb),z,1),.tabelaPed,"/")
. ;
. set codPedido=""
. for set codPedido=$order(tabelaPed(codPedido)) quit:codPedido="" do
. . ;
. . set ItemPedido=""
. . for set ItemPedido=$order(tabPedidoOriginal(codPedido,ItemPedido)) quit:ItemPedido="" do
. . . set ^mtempT.CCPVSC101(codTerminal,1,1,1,1,1,1,1,seqComb,codPedido,ItemPedido)=""
;
;merge ^g=^mtempT.CCPVSC101
;
quit $$$OK
;
ReordenarGeracaoSugestaoInf() ;
quit "1,1,2,GC"
;
TESTE2(tabPedido,tabEstoque,qtdRecursividade,tabCombinacaoSuficiente) ;
$$$VAR
new i,codPedido,stringPedido,tabPedidoDeduzido,qtdPedidos,listaDePedidos,combinations,encontradoMelhorCombinacao
;
set ^m=^m+1
m ^h(^m)=tabEstoque
set sc=$$FiltrarPedidoSemSaldoParaSi(.tabPedido,.tabEstoque,.tabPedidoDeduzido,qtdRecursividade)
m ^j(^m)=tabPedidoDeduzido
if '$data(tabPedidoDeduzido) s ^p(^m)=1 quit $$$Error("Não há pedidos que comtemplem saldo em pelo menos 1 produto/cor/tamanho!")
;
set (codPedido,stringPedido)=""
for set codPedido=$order(tabPedidoDeduzido(codPedido)) quit:codPedido="" do
. if stringPedido="" set stringPedido=codPedido
. else set stringPedido=stringPedido_y_codPedido
;
s ^x(1,^m)=stringPedido
set listaDePedidos=$ListFromString(stringPedido,y)
set qtdPedidos=$ListLength(listaDePedidos)
;
s ^x(2,^m)=listaDePedidos
; Quando encontrado uma combinação que atenda o requisito, variavel abaixo controla para terminar o loop de busca
; pois pode ocorrer de uma qtd menor de combinação de pedidos gastar um saldo maior de estoque, no entanto
; despachar uma maior quantidade de pedidos é prioritário em relação a quantidade de estoque que irá consumir.
set encontradoMelhorCombinacao=0
for i=qtdPedidos:-1:2 do
. if encontradoMelhorCombinacao=1 quit
. ;
. set sc=$$PriorizarCombinacoes(listaDePedidos,i,.tabEstoque,.tabPedidoDeduzido,.combinations,.encontradoMelhorCombinacao,.tabPedido,qtdRecursividade,.tabCombinacaoSuficiente,stringPedido)
;
;if $data(tabPedido) set sc=$$TESTE2(.tabPedido,.tabEstoque)
;
quit $$$OK
;
FiltrarPedidoSemSaldoParaSi(tabPedido,tabEstoque,tabPedidoDeduzido,qtdRecursividade) ;
$$$VAR
new codPedido,fruta,codItemPedido
;
kill tabPedidoDeduzido
merge tabPedidoDeduzido=tabPedido
;
; Na primeira iteração tentará encontrar combinações que somente atendam totalmente o pedido.
if qtdRecursividade=1 do
. set (codPedido,codItemPedido,fruta)=""
. for set codPedido=$order(tabPedido(codPedido)) quit:codPedido="" do
. . for set codItemPedido=$order(tabPedido(codPedido,codItemPedido)) quit:codItemPedido="" do
. . . for set fruta=$order(tabPedido(codPedido,codItemPedido,fruta)) quit:fruta="" do
. . . . ;
. . . . set qtdSolicitada=$piece(tabPedido(codPedido,codItemPedido,fruta),z,1)
. . . . set qtdEstoque=$piece(tabEstoque(fruta),z,1)
. . . . ;
. . . . if qtdSolicitada<=qtdEstoque quit
. . . . ;
. . . . ;b ; 2
. . . . kill tabPedidoDeduzido(codPedido)
;
quit $$$OK
; Nas demais iterações tentará encontrar combinações que tenha atendimento total de um ou mais itens dentro do pedido.
; Verifica quando itens o pedido tem para atender, em seguida vai descontando itens que não tenham estoque suficiente
; para atender a sí de forma isolada, caso não sobre itens para atender parcial, removera da lista de prioritário.
if qtdRecursividade>=2 do
. ;
. quit
. ;
. set (codPedido)=""
. for set codPedido=$order(tabPedido(codPedido)) quit:codPedido="" do
. . ;
. . set (codItemPedido,fruta)="",qtdProdutoPedido=0
. . for set codItemPedido=$order(tabPedido(codPedido,codItemPedido)) quit:codItemPedido="" do
. . . for set fruta=$order(tabPedido(codPedido,codItemPedido,fruta)) quit:fruta="" do
. . . . ;
. . . . set qtdProdutoPedido=qtdProdutoPedido+1
. . ;
. . set (codItemPedido,fruta)=""
. . for set codItemPedido=$order(tabPedido(codPedido,codItemPedido)) quit:codItemPedido="" do
. . . for set fruta=$order(tabPedido(codPedido,codItemPedido,fruta)) quit:fruta="" do
. . . . ;
. . . . set qtdSolicitada=$piece(tabPedido(codPedido,codItemPedido,fruta),z,1)
. . . . set qtdEstoque=$piece(tabEstoque(fruta),z,1)
. . . . ;
. . . . if qtdSolicitada<=qtdEstoque quit
. . . . ;
. . . . set qtdProdutoPedido=qtdProdutoPedido-1
. . ;
. . ;m ^j=tabPedidoDeduzido
. . if qtdProdutoPedido=0 kill tabPedidoDeduzido(codPedido)
. . ;m ^k=tabPedidoDeduzido
;
quit $$$OK
;
TXT(listaDePedidos) ;
$$$VAR
;
;
;
quit $$$OK
;
;/////////////////////////////
;
PriorizarCombinacoes(listaDePedidos,variacoes,tabEstoque,tabPedidoDeduzido,combinations,encontradoMelhorCombinacao,tabPedido,qtdRecursividade,tabCombinacaoSuficiente,stringPedido) ;
$$$VAR
new i,combinacao,codPedido
kill tabCombinacaoSuficiente
;
;set sc=$$TXT(.stringPedido)
;s ^x(100)=sc
;m ^x(99)=stringPedido
;
;quit $$$OK
;
; Função para gerar combinações
set (combinacao)=""
do GenerateCombinations(listaDePedidos,"",variacoes,.combinations,qtdRecursividade)
;
m ^k(1,^m)=combinations
set i=""
for set i=$order(combinations(i)) quit:i="" do
. ;
. if $extract(combinations(i),1)="/" set combinations(i)=$extract(combinations(i),2,*)
;
/*
; Imprimindo as combinações
write !,"Combinações de ",variacoes," letras:",!
set i=0
for i=1:1:combinations {
write combinations(i)_" ",!
}
*/
m ^k(2,^m)=combinations
;b ;1
set sc=$$ValidarCombMaiorQtdPedidos(.combinations,.tabEstoque,.tabPedidoDeduzido,.tabCombinacaoSuficiente)
m ^l(^m)=tabCombinacaoSuficiente
if $$$ISERR(sc) quit $$$OK
if $$$ISOK(sc) set encontradoMelhorCombinacao=1
;
set sc=$$AtualizarPrioriacao(.tabPedido,.tabEstoque,.tabPedidoDeduzido,.tabCombinacaoSuficiente)
;
;m ^c=tabCombinacaoSuficiente
;s ^m=$increment(^m)
;merge ^b(^m,"a")=tabPedido
;merge ^b(^m,"b")=tabEstoque
;
set sc=$$$OK
if $data(tabPedido) set sc=$$TESTE2(.tabPedido,.tabEstoque,qtdRecursividade+1)
if $$$ISERR(sc) do
. kill tabCombinacaoSuficiente(999)
. set codPedido=""
. for set codPedido=$order(tabPedido(codPedido)) quit:codPedido="" do
. . if '$data(tabCombinacaoSuficiente(999)) set tabCombinacaoSuficiente(999)=codPedido
. . else set tabCombinacaoSuficiente(999)=tabCombinacaoSuficiente(999)_"/"_codPedido
;
quit $$$OK
;
; Função para gerar combinações recursivamente
GenerateCombinations(listaDePedidos,current,variacoes,combinations,qtdRecursividade) ;
$$$VAR
new i,letter,newLetters,qtdPedidos,elemento,novaListaDePedidos
;
s ^z($now(),variacoes)=""
set qtdPedidos=$ListLength(listaDePedidos)
;
if variacoes=0 do quit $$$OK
. s ^x(3,^m)=current
. set combinations($increment(combinations))=current
. m ^x(4,^m)=combinations
;
set i=0
for i=1:1:qtdPedidos {
;
set pedido=$list(listaDePedidos,i)
set novaListaDePedidos=$list(listaDePedidos,i+1,*) ; Remove letras já usadas
;
do GenerateCombinations(novaListaDePedidos,current_"/"_pedido,variacoes-1,.combinations,qtdRecursividade)
s ^x(5,^m,variacoes,i)=""
}
;
quit $$$OK
;
ValidarCombMaiorQtdPedidos(combinations,tabEstoque,tabPedidoDeduzido,tabCombinacaoSuficiente) ;
$$$VAR
new combinacao,codPedidoCombinacao,codFruta,qtdNecessidadeFruta,tabNecessidadeFrutaGrupoPed,outraCombinacao
new qtdAcumuladaCombinacao,qtdAcumuladaOutraCombinacao,tabCombinacaoQtd
kill tabNecessidadeFrutaGrupoPed,qtdEstoqueFrutaInsuficiente,tabCombinacaoQtd,codItemPedido
;
set (combinacao,qtdEstoqueFrutaInsuficiente)=""
for set combinacao=$order(combinations(combinacao)) quit:combinacao="" do
. ;
. kill tabNecessidadeFrutaGrupoPed
. set qtdAcumuladaCombinacao=0
. ;
. for i=1:1:$l(combinations(combinacao),"/") do
. . ;
. . set codPedidoCombinacao=($piece(combinations(combinacao),"/",i))
. . ;
. . ;b ;1
. . set (codItemPedido,codFruta)=""
. . for set codItemPedido=$order(tabPedidoDeduzido(codPedidoCombinacao,codItemPedido)) quit:codItemPedido="" do
. . . for set codFruta=$order(tabPedidoDeduzido(codPedidoCombinacao,codItemPedido,codFruta)) quit:codFruta="" do
. . . . ;
. . . . set qtdNecessidadeFruta=$piece(tabPedidoDeduzido(codPedidoCombinacao,codItemPedido,codFruta),z,1)
. . . . ;
. . . . set tabNecessidadeFrutaGrupoPed(codFruta)=$get(tabNecessidadeFrutaGrupoPed(codFruta))+qtdNecessidadeFruta
. . . . ;
. . . . ;b ;1
. . . . if tabNecessidadeFrutaGrupoPed(codFruta)>tabEstoque(codFruta) set qtdEstoqueFrutaInsuficiente=1
. . . . ;
. . . . set qtdAcumuladaCombinacao=qtdAcumuladaCombinacao+qtdNecessidadeFruta
. . ;
. ;
. ;if combinacao=14 b ;1
. ; Caso alguma fruta da combinação quando somando todas a necessidades da mesma ultrapasse a quantidade atual
. ; de etoque não seta como uma combinação valida
. if qtdEstoqueFrutaInsuficiente=1 set qtdEstoqueFrutaInsuficiente="" quit
. ;
. ;b ;1
. set qtdAcumuladaOutraCombinacao=0
. set outraCombinacao=$order(tabCombinacaoQtd(""))
. if outraCombinacao'="" set qtdAcumuladaOutraCombinacao=$get(tabCombinacaoQtd(outraCombinacao))
. ;
. ;b ; 2
. if qtdAcumuladaOutraCombinacao>qtdAcumuladaCombinacao quit
. ;
. ;b ;3
. ;
. if outraCombinacao'="" do
. . kill tabCombinacaoSuficiente(outraCombinacao)
. . kill tabCombinacaoQtd(outraCombinacao)
. merge tabCombinacaoSuficiente(combinacao)=combinations(combinacao)
. set tabCombinacaoQtd(combinacao)=qtdAcumuladaCombinacao
. ;
;
if '$data(tabCombinacaoSuficiente) quit $$$Error("Não encontrado combinação com saldo suficiente para os agrupamentos de pedidos!")
;
quit $$$OK
;
AtualizarPrioriacao(tabPedido,tabEstoque,tabPedidoDeduzido,tabCombinacaoSuficiente) ;
$$$VAR
new combinacao,i,codFruta,codPedido,qtdUtilizadaFruta,tabTotalFruta,codItemPedido
;
kill tabTotalFruta
;
set combinacao=""
for set combinacao=$order(tabCombinacaoSuficiente(combinacao)) quit:combinacao="" do
. ;
. for i=1:1:$l(tabCombinacaoSuficiente(combinacao),"/") do
. . ;
. . set codPedido=$piece(tabCombinacaoSuficiente(combinacao),"/",i)
. . ;
. . set (codItemPedido,codFruta)=""
. . for set codItemPedido=$order(tabPedido(codPedido,codItemPedido)) quit:codItemPedido="" do
. . . for set codFruta=$order(tabPedido(codPedido,codItemPedido,codFruta)) quit:codFruta="" do
. . . . ;
. . . . set qtdUtilizadaFruta=$piece(tabPedido(codPedido,codItemPedido,codFruta),z,1)
. . . . ;
. . . . set tabTotalFruta(codFruta)=$get(tabTotalFruta(codFruta))+qtdUtilizadaFruta
. . ;
. . kill tabPedido(codPedido)
;
;s ^m=$increment(^m)
;merge ^b(^m,"a")=tabPedido
;merge ^b(^m,"b")=tabEstoque
;
; Desconta do saldo de estoque utilizado nos calculos a quantidade que será distribuida nos pedidos que encaixaram
; como atendiveis
set codFruta=""
for set codFruta=$order(tabEstoque(codFruta)) quit:codFruta="" do
. ;
. ; Se não houve desconto do item
. if '$data(tabTotalFruta(codFruta)) quit
. ;
. set $piece(tabEstoque(codFruta),z,1)=$piece(tabEstoque(codFruta),z,1)-$piece(tabTotalFruta(codFruta),z,1)
;
quit $$$OK
;
;
; csw:csp:naogerarObjectScriptObjectScriptProduct version: IRIS 2024.1
$ZV: intersystem iris cache
Está dificil de entender o que você precisa. Você quer todas as possíveis combinações da global ˆx(1,1) ? E qual a relação disso com o código?
Bom dia.
Obrigado pelo interesse no tópico.
No caso teria que encontrar todas as possíveis combinações de codPedido. O dado incialmente vem da ^mtempT.CCPVSC101 e sofre uma serie de filtragens por conta de estoque suficiente por exemplo.
Até o ponto que se encontra uma lista de string desses pedidos, onde recursivamente ele encontra combinações do tipo
Para listas curtas como por exemplo 20 pedidos ele gera até 1.200.000 +-, o que não é um problema, porem as listas as vezes passam de 100 pedidos onde gera números de combinações exorbitantes, passa da casa de trilhões. O que torna a execução bem demorada. No caso as combinações são por exemplo: [1,2,3,4]
1,2,3,4
1,2,3
1,2,4
1,3,4
etc...
If I understand you correctly, you want for a given number of objects all the possible combinations? That is, if we have 3 objects (3 numbers, 3 words or whatever) then you want:
1 of 3 (3 possibilities): (1) (2) (3)
2 of 3 (3 possibilities): (1,2) (1,3) (2,3)
3 of 3 (1 possibility) : (1,2,3)
For 3 objects there are in sum 7 possible combinations (see above). Your ^x(1,1) string contains 137 items. I'm pretty sure, you will never see that mutch combination...
Here some numbers for all possible combinations for: 1 item : 1 10 items: 1,023 20 items: 1,048,575 50 items: 1,125,899,906,842,623 75 items: 37,778,931,862,957,161,730,000 100 items: 1,267,650,600,228,229,401,000,000,000,000 137 items: 174,224,571,863,520,493,300,000,000,000,000,000,000,000A year has 365.25*86400, that are 31,557,600 seconds. With another words, you would need a computer system, which is able to genarate 5.5 * 10^33 combinations each second! I don't have such a beast, and I'm sure, you too.
Anyway, maybe the below class gives you some clue, how to compute and how to generate combinations. One more note, recursion is the tool to make (some) solutions clear and simple but recursion in loops, especially in loops with thousands or millions of passes, isn't a good idea. Beside of resources (stack, memory) for each new call a stackframe must be prepared and after the call removed again. This costs time, much time. Try that Times() method in the below class.
/// Some math functions Class DC.Math Extends %RegisteredObject { /// Factorial by multiplication (the more practical way) /// Return n! /// ClassMethod MulFact(n) { for i=2:1:n-1 set n=n*i quit n+'n } /// Factorial by recursion (the way, people learn recursion in the school) /// Return n! /// ClassMethod RecFact(n) { quit $select(n>1:n*..RecFact(n-1),1:1) } /// There is a noticeable time difference between MulFact() and RecFact(). /// /// Recursion helps to keep an algorithm clear an simple but needs more /// resources - for a few loops it's OK, but for many loops it's a no-go /// (beside a stack space, a stack frame must be prepared for each loop cycle) ClassMethod Times(n) { while $zh#1 {} s t1=$zh f i=1:1:1E6 { d ..MulFact(n) } s t1=$zh-t1 while $zh#1 {} s t2=$zh f i=1:1:1E6 { d ..RecFact(n) } s t2=$zh-t2 write " Fact:",$j(t1,10,4),!,"Rfact:",$j(t2,10,4),!," Diff:",$j(t2-t1/t1*100,8,2),"%",! } /// The Holy Trinity of the statistic functions: permutations, combinations and variations /// /// Here we go with the combinations. /// /// Return the number of combinations (without repetition) of K elements from a set of N objects /// /// The number of possible combinations is: N over K /// which is the same as: N! / (K! * (N-K)!) /// /// Note: /// one can't make a direct use of the (above) Factorial function /// because the MAXNUM limit will be hit very soon ClassMethod Comb(k, n) { set c=1 for k=1:1:k { set c=c/k*n, n=n-1 } quit c } /// Return the sum of all possible combinations of N objects /// i.e. (1-of-n) + (2-of-n) + (3-of-n) + ... + (n-of-n) /// ClassMethod AllComb(n) { set s=0 for i=1:1:n { set s=s+..Comb(i,n) } quit s } /// Generate a list of combinations for K elements of N objects /// ClassMethod GenComb(k, n) { for i=1:1:k set e(i)=n-k+i set s=0, c(0)=0 10 set s=s+1, c(s)=c(s-1) 14 for c(s)=c(s)+1:1:e(s) goto 10:s<k do ..work1(.c,s) 16 set s=s-1 if s goto 14:c(s)<e(s),16 } /// This method is the workhorse /// either, print the combinations (one k-tuple at time) /// or do your own task. ClassMethod work1(c, s) [ Internal ] { write "(" for i=1:1:s write:i>1 "," write c(i) write ")",! } /// For example, you could use that ^x(1,1) string /// ClassMethod work2(c, s) { set t=^x(1,1) write "(" f i=1:1:s write:i>1 "," write $p(t,",",c(i)) write ")",! } /// save each combination (OK, c(0) should be killed) /// ClassMethod work3(c, s) { m ^mtemp("comb",$i(^mtemp("comb")))=c } }write ##class(...).Comb(3,4) to compute the combinations 3-of-4 (3 items of 4 objects)
write ##class(...).AllComb(3) to compute all combinations of 3 objects (1-of-3 plus 2-of-3 plus 3-of-3)
do ##class(...).GenComb(3,4) to show all 3-of-4 combinations
For all possible combinations of N objects you must do a loop:
for i=1:1:N do ##class(...).GenComb(i,N)
Wut? Don't we have a tail-call elimination? 😨
First, my experience with tail recursion is very limited,
second, after adding the TailFact() method and a little change to Times() method in the above class, I must say, I don't see any benefit of the TailFact() method. Quite the contrary, now the function have to push two values on the stack instead of one...
/// Factorial using tail_recursion /// ClassMethod TailFact(n) { quit ..tfact(n,1) } ClassMethod tfact(n, f) { quit $select(n>1:..tfact(n-1,f*n),1:f) } /// There is a noticeable time difference between MulFact() and RecFact(). /// /// Recursion helps to keep an algorithm clear an simple but needs more /// resources - for a few loops it's OK, but for many loops it's a no-go /// (beside a stack space, a stack frame must be prepared for each loop cycle) ClassMethod Times(n) { while $zh#1 {} s t1=$zh f i=1:1:1E6 { d ..MulFact(n) } s t1=$zh-t1 while $zh#1 {} s t2=$zh f i=1:1:1E6 { d ..RecFact(n) } s t2=$zh-t2 while $zh#1 {} s t3=$zh f i=1:1:1E6 { d ..TailFact(n) } s t3=$zh-t3 write " Fact:",$j(t1,10,4),!,"Rfact:",$j(t2,10,4),!,"Tfact:",$j(t3,10,4),! write "RDiff:",$j(t2-t1/t1*100,8,2),"%",!,"TDiff:",$j(t3-t1/t1*100,8,2),! }and here some time values
USER>d ##class(DC.Math).Times(5) Fact: 0.3306 Rfact: 1.2199 Tfact: 1.4219 RDiff: 268.97% TDiff: 330.07 USER>d ##class(DC.Math).Times(10) Fact: 0.4433 Rfact: 2.3913 Tfact: 2.5549 RDiff: 439.40% TDiff: 476.28 USER>d ##class(DC.Math).Times(20) Fact: 0.7034 Rfact: 4.8017 Tfact: 5.2183 RDiff: 582.63% TDiff: 641.86So the conclusion is the compiler doesn't have tail-call elimination.