Identificar composição de um número dentro de uma lista de valores

[nicolasdeldalle]

Bom dia ! 

Estou com um problema recorrente e gostaria de saber se alguém já conseguiu resolver. 

Tenho uma lista grande lista de valores (mais de 1000), podendo ser positivos ou negativos. Dentro desses valores, sei que a soma de alguns resulta em um valor que estou procurando. 

Para dar um exemplo, tenho a seguinte lista:

Lista
10,32
101,43
200
-134,93
435,97
345,74
-869,34
749,31
-538,48
573,89
-347,95
453,35
74,85
-435,78
-647,95

Meu objetivo é encontrar qualquer combinação de números presentes nessa lista que somam até: 

Target

-187,34

Podem existir várias combinações (apesar desse caso ter apenas uma). 

Alguém conhece alguma maneira de resolver esse problema com Alteryx? 

Obrigado !!

[fmvizcaino]

Bom dia @nicolasdeldalle , tudo bem?

Para criar essa solução, precisei criar uma macro iterativa que fosse capaz de me gerar todas as combinações possíveis de números automaticamente independente do número de valores que a base inicial tivesse.

O workflow e macro ficaram da seguinte forma:

Um cuidado a ser tomado (em vermelho) é relacionado ao número de combinações que o workflow cria, como você citou que possui + de 1000 valores, para obtermos todas as combinações possíveis e imagináveis com eles (sem eliminar todas as milhares de duplicações no meio do caminho) seria 1000 ^ 1000, o que torna a combinação de todos inviável. Pensando nisso, inseri aquela fórmula para você definir o número de valores máximo que gostaria de combinar.

Em relação a macro, tentei explicar todos os passos, mas o resumo da obra é a geração de todas as possíveis combinações. Acabei decidindo por remover todas as duplicidades no final do workflow acima.

Sei que você já viu macros iterativas (foi eu quem deu um treinamento para o seu time uns anos atrás rs) mas estarei compartilhando o tutorial que mostra pontos relevantes do desenvolvimento da mesma.

https://community.alteryx.com/t5/Videos/Build-Your-First-Iterative-Macro/td-p/55565

Abs,

Fernando Vizcaino

[fmvizcaino]

Atualizei o workflow e macro com o número de iterações sendo o número de combinações, i.e. iter=2 significando 2 números combinados.

Além disso, transformei os possíveis resultados em decimal fixo para arredondar e conseguir encontrar o valor esperado.

[nicolasdeldalle]

Obrigado pela ajuda Fernando, 

Vejo que essa solução funcionaria em casos de poucas combinações, mas considerando que tenho bases de milhares de valores (até valores repetidos), e que a composição do valor que estou procurando pode ser de um grande número de valores (meu valor target poderia ser a soma de 60 valores da minha lista, por exemplo), acho que dessa forma nunca vou conseguir resolver meu problema. 

Pensei em usar o Python que talvez poderia trazer alguns algoritmos mais eficientes para esse tipo de problema, mas não tenho conhecimentos suficientes... 

Imagino que alguém no mundo já deve ter resolvido um caso desses, que é bastante comum em fraude por exemplo... 

De qualquer forma, obrigado pela sugestão !

Abs 

[fmvizcaino · Accepted solution]

Oi @nicolasdeldalle ,

Dei uma pesquisada por aí e encontrei esse algoritmo.

https://www.rdocumentation.org/packages/utils/versions/3.6.2/topics/combn

Aparentemente ele consegue criar combinações de forma otimizada, mas até onde entendi, você precisa criar um loop para quantidade de números que deseja nas combinações. Tem a possibilidade de já calcular a soma dos valores inclusive, dê uma olhada e veja se ajuda.

De qualquer forma, como sua análise combinatória é muito aberta, embora consigamos otimizar o processo, ele ainda será bastante lento e exponencialmente relacionado ao número de valores.

Abs,

Fernando Vizcaino

[nicolasdeldalle]

Obrigado Fernando, 

Vou continuar pesquisando, me falaram que algoritmos genéticos e de otimização poderiam me ajudar. 

Abs 

[FláviaB]

Obrigada pela ajuda, @fmvizcaino!

@nicolasdeldalle, fique à vontade para compartilhar com a gente se encontrar uma solução.