Recursivity

Question

Question

alex petryr · Nov 4

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:naogerar

Product version: IRIS 2024.1

$ZV: intersystem iris cache

Discussion (6)2

Log in or sign up to continue

score 0 · Answer 1 · 2024-11-05T09:00:50-05:00

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?

score 0 · Answer 2 · 2024-11-05T09:08:24-05:00

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

score 3 · Answer 3 · 2024-11-05T20:17:16-05:00

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,000

A 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)

score 0 · Answer 4 · 2024-11-06T06:04:01-05:00

Jani Hurskainen · Nov 6

Wut? Don't we have a tail-call elimination? 😨

0 0

score 0 · Answer 5 · 2024-11-06T08:32:58-05:00

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.86

score 0 · Answer 6 · 2024-11-06T23:48:57-05:00

Jani Hurskainen · Nov 6

So the conclusion is the compiler doesn't have tail-call elimination.

0 0