Crossing values in array

It took me 8 hours to develop the algorithm, but it was worth the challenge.

Here is the code:

<?php
$total = 3.60; // valor total a ser testado
echo "Para um total de $total:\n\n";
$dados = array('0.10','0.20','0.30','0.50',
               '3.00','3.30','4.00','5.00',
               '1.00','1.10','2.00','2.20');
foreach ($dados as $d) 
    $dadosf[] = floatval($d); // cria array paralelo em float para facilitar

for ($i = 0; $i < sizeof($dados) - 1; $i++) 
    $base[]=array($i); // cria os primeiros valores de base

for ($n = 2;$n < sizeof($dados); $n++) {
    foreach ($base as $i => $b1) { // soma os números de base
        $soma_base[$i]=0;
        foreach ($b1 as $b2) {
            $soma_base[$i] += $dadosf[$b2];
        }
    }
    $base2 = [];
    for ($b = 0; $b < sizeof($base); $b++) {
        $u = sizeof($base[$b])-1; // último elemento da base
        for ($p = $base[$b][$u] + 1; $p < sizeof($dados); $p++) {
            if (number_format($soma_base[$b] + $dadosf[$p], 3) == 
                number_format($total, 3)) { 
            // *** encontrou combinação da soma ***             
                echo 'Combinação ' . ++$c . ': ';
                for ($d = 0; $d <= $u; $d++) { 
                    echo $dados[$base[$b][$d]] . ' + ';
                }
                echo $dados[$p] . ' = ' . $total . "\n";
            }
            $base2[] = $base[$b];
            $base2[sizeof($base2)-1][] = $p;
        }
    }
    $base = $base2;
}

In this example, using 3.6 as the value to compare, the result will be:

Para um total de 3.6:

Combinação 1: 0.30 + 3.30 = 3.6
Combinação 2: 0.10 + 0.20 + 3.30 = 3.6
Combinação 3: 0.10 + 0.50 + 3.00 = 3.6
Combinação 4: 0.30 + 1.10 + 2.20 = 3.6
Combinação 5: 0.50 + 1.10 + 2.00 = 3.6
Combinação 6: 0.10 + 0.20 + 0.30 + 3.00 = 3.6
Combinação 7: 0.10 + 0.20 + 1.10 + 2.20 = 3.6
Combinação 8: 0.10 + 0.30 + 1.00 + 2.20 = 3.6
Combinação 9: 0.10 + 0.50 + 1.00 + 2.00 = 3.6
Combinação 10: 0.20 + 0.30 + 1.10 + 2.00 = 3.6
Combinação 11: 0.10 + 0.20 + 0.30 + 1.00 + 2.00 = 3.6

The code is at link

The basis of logic is a combinatorial analysis. Using a fictitious array below, for example, 5 elements, the combinations should be as follows:

+-------------+-----------+---------+-----------+
| Elementos   | 1,2,3,4,5 |         |           |
+-------------+-----------+---------+-----------+
| Combinações |           |         |           |
+-------------+-----------+---------+-----------+
| Nível 2     | Nível 3   | Nível 4 | Nível 5   |
+-------------+-----------+---------+-----------+
| 1,2         | 1,2,3     | 1,2,3,4 | 1,2,3,4,5 |
+-------------+-----------+---------+-----------+
| 1,3         | 1,2,4     | 1,2,3,5 |           |
+-------------+-----------+---------+-----------+
| 1,4         | 1,2,5     | 1,3,4,5 |           |
+-------------+-----------+---------+-----------+
| 1,5         | 1,3,4     | 2,3,4,5 |           |
+-------------+-----------+---------+-----------+
| 2,3         | 1,3,5     |         |           |
+-------------+-----------+---------+-----------+
| 2,4         | 1,4,5     |         |           |
+-------------+-----------+---------+-----------+
| 2,5         | 2,3,4     |         |           |
+-------------+-----------+---------+-----------+
| 3,4         | 2,3,5     |         |           |
+-------------+-----------+---------+-----------+
| 3,5         | 2,4,5     |         |           |
+-------------+-----------+---------+-----------+
| 4,5         | 3,4,5     |         |           |
+-------------+-----------+---------+-----------+

Notice that each subsequent level contains a derivation of the elements of the previous level.

ISSUE:

  

This solution will only be feasible for a limited number of items, not   space, but due to processing time due to the large number of   combinations.

     

To know how many combinations can be found between all   items to be compared, this is the formula:

     

    

So,ifthe$dadosarrayhasonly30items,forexample,thenumberofpossiblecombinationswouldbe2^30-1=1,073,741,823;iftheyare100items=  1.26765E+30!!!

    

Youcanalsocalculatehowmanycombinationsarepossibleperlevel,iecombinationwith2numberstogether,3numbers,andsoon.Inthiscasetheformulais:

    

     

... where n = total number of items and k = current level.   Ex: to know how many combinations are possible in a sequence of 5 numbers, within level 2: 5! / (2! * (5 - 2)!) = 10. That is, if we make a comparison for the sequence 1, 2, 3, 4, 5 , in level 2 of the comparison (1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5) = 10 items .

This second answer solves the RAM limitation issue: MySql!

If in the first answer I took 8 hours, I will not say how much I spent on this, otherwise they will think I'm crazy! ... rsrsrs

I re-created the entire algorithm so that large arrays are used in database tables.

In this way, the number of combinations is virtually unlimited, only depending on the disk space.

It's worth noting that although this second approach solves the problem of RAM overflow, the downside is that it will be absurdly slower. I mean, if it is to do the process with for example 100 values, put the computer to work and go to sleep ...:)

Check out an example working in MySql at this link: link

In summary, to work, just:

Below the code:

<?php
$total = 3.6; // preencher com valor total a ser testado
$num_dados = 12; // preencher com o total de números que serão gerados para teste

$time_start = microtime(true); // cronometra o tempo total de processamento

// ****************** CONEXÃO COM BANCO DE DADOS **************************
$servername = "localhost"; // nome do servidor
$username = "root"; // nome do usuario
$password = ""; // senha
$dbname = "comb"; // nome do banco de dados

$db = mysqli_connect($servername, $username, $password, $dbname);
if (!$db) {
    die("Falha na conexão: " . mysqli_connect_error());
}

cria_tabela($db, 'dados', 1);
cria_tabela($db, 'base',  2, 'int(10) UNSIGNED NOT NULL');
cria_tabela($db, 'resultados',  1, 'varchar(10000)');

gera_dados($db, $num_dados); // gera x registros de dados float

//******************** ALGORITMO ***********************

$cont_combina = 0;
echo "Para um total de $total:\n\n";

// carrega dados no array $dados --------------------

$result = mysqli_query($db, 'SELECT * FROM dados');
while ($row = mysqli_fetch_assoc($result))
    $dados[] = $row['valor'];

// testa se existe o valor (sem soma) dentro de $dados
if (in_array($total, $dados))
    echo "1 nível\nCombinação " . ++$cont_combina . ': ' . number_format($total, 2) . ' = ' . number_format($total, 2) . "\n\n";

// cria os primeiros valores de base-----------------
$key1 = 0; $key2 = 0;
for ($i = 0; $i < sizeof($dados) - 1; $i++) { // base são sempre a soma dos valores anteriores exceto 1 à direita que será comparado
    $sql = "INSERT INTO base (key1, key2, valor) VALUES ($key1, 0, $i)";
    mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao inserir registro na tabela 'base'");
    $key1++;
}

// processa as combinações gerais --------------------
for ($nivel = 1;$nivel < sizeof($dados) - 1; $nivel++) {
    echo "-------------------------\n" . ($nivel+1) . " níveis (";
    printf("%d", $nivel * 100 / (sizeof($dados) - 1));
    echo "%)\n";

// soma os números de base-----------------------------
    cria_tabela($db, 'soma_base', 1);

    $sql = "INSERT INTO soma_base (key1, valor)
              SELECT base.key1, SUM(dados.valor) FROM base 
                INNER JOIN dados ON base.valor = dados.key1 
                GROUP BY base.key1";
    mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao gerar registros na tabela 'soma_base'");

    $result = mysqli_query($db, "SELECT * FROM soma_base ORDER BY key1 DESC LIMIT 1");
    if (!$soma_base = mysqli_fetch_assoc($result)) die ("erro leitura tabela 'soma_base'");
    $ult_combinacao = $soma_base['key1'];

    // análise combinatória -----------------------------
    cria_tabela($db, 'base_ant', 2, 'int(10) UNSIGNED NOT NULL');
    $key1_base_ant = 0;

    for ($combinacao = 0; $combinacao < $ult_combinacao; $combinacao++) {
        // acha valor do último elemento da base atual para calcular o próximo
        $result2 = mysqli_query($db, 'SELECT count(*) AS tot_elem_key1 FROM base WHERE key1 = ' . $combinacao);  // total elementos key1
        $base2 = mysqli_fetch_assoc($result2);
        $tot_elem_key1 = $base2['tot_elem_key1'] - 1;

        $result2 = mysqli_query($db, 'SELECT * FROM base WHERE key1 = ' . $combinacao . ' AND key2 < 9999999999 ORDER BY key1, key2 DESC');  //acha último elemento da base
        if (!$base2 = mysqli_fetch_assoc($result2)) die ("não achou último elemento");
        // $p = ponteiro para valor o valor a ser comparado. Ex: soma dos valores base + valor indicado pelo ponteiro
        for ($p = $base2['valor'] + 1; $p < sizeof($dados); $p++) { // pega o valor do último elemento da base atual + 1 (próximo elemento)
            $result3 = mysqli_query($db, 'SELECT * FROM soma_base WHERE key1 = ' . $combinacao);  // acha soma deste nível
            if (!$soma_base = mysqli_fetch_assoc($result3)) die ("não achou soma base");
//            if ($soma_base['valor'] >= $total) break;
            if (number_format($soma_base['valor'] + $dados[$p], 4) == number_format($total, 4)) { // *** encontrou combinação da soma ***
                // mostra combinação encontrada  -------------------
                echo 'Combinação ' . ++$cont_combina . ': ';
                $d = 0;
                $result5 = mysqli_query($db, 'SELECT * FROM base WHERE key1 = ' . $combinacao);
                $numeros = []; // armazena resultados num array para gravar em tabela
                while ($base5 = mysqli_fetch_assoc($result5) and $d <= $tot_elem_key1) {
                    echo number_format($dados[$base5['valor']], 2) . ' + ';
                    $numeros[] = floatval($dados[$base5['valor']]);
                    $d++;
                }
                echo number_format($dados[$p], 2) . ' = ' . number_format($total, 2) . "\n";
                $numeros[] = floatval($dados[$p]);
                $sql = "INSERT INTO resultados (key1, valor) VALUES ($cont_combina, '" . serialize($numeros) . "')"; // grava resultado encontrado
                mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao inserir registro na tabela 'resultados'");
            }

            // transfere base para base_ant  -------------------
            $result4 = mysqli_query($db, 'SELECT * FROM base WHERE key1 = ' . $combinacao);
            while ($base4 = mysqli_fetch_assoc($result4)) {
                $key2 = $base4['key2'];
                $valor = $base4['valor'];
                $sql = "INSERT INTO base_ant (key1, key2, valor) VALUES ($key1_base_ant, $key2, $valor)";
                mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao inserir registro na tabela 'base_ant'");
                $key2++;
            }
            $sql = "INSERT INTO base_ant (key1, key2, valor) VALUES ($key1_base_ant, $key2, $p)";
            $key1_base_ant++;
            mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao inserir registro 2 na tabela 'base_ant'");
        }
    }
    mysqli_query($db, "DROP TABLE base") or die(mysqli_error($db));
    mysqli_query($db, "RENAME TABLE base_ant TO base") or die(mysqli_error($db));
}

mysqli_close($db);
echo "\n(100%)\n";
$time_end = microtime(true);
$execution_time = ($time_end - $time_start)/60;
echo "Tempo total de execução: " . number_format($execution_time, 2) . " Minutos\n";

return;

//---------------------------------------------------------------------------------------------

function cria_tabela($db, $tabela, $campos_chave, $tipo_valor = "float UNSIGNED NOT NULL") {
    $sql = "DROP TABLE IF EXISTS $tabela";
    mysqli_query($db, $sql) or die(mysqli_error($db));
    $sql = "CREATE TABLE $tabela (";
    if ($campos_chave > 0) $sql .=   "key1 int(10) UNSIGNED NOT NULL";
    if ($campos_chave > 1) $sql .= ", key2 int(10) UNSIGNED NOT NULL";
    if ($campos_chave > 0) $sql .=   ", ";
    $sql .= "valor $tipo_valor)";
    mysqli_query($db, $sql) or die(mysqli_error($db) . "\nNão foi possível criar tabela '$tabela'"); 
    if ($campos_chave > 0) { // cria índice
        $sql = "ALTER TABLE $tabela ADD PRIMARY KEY (key1";
        if ($campos_chave > 1) $sql .=   ",key2";
        $sql .=")";
        mysqli_query($db, $sql) or die(mysqli_error($db) . "\nNão foi possível criar índice para tabela '$tabela'");
    }
}

function gera_dados($db, $num) {
    for ($i = 1; $i<=$num; $i++) {
        $sql = "INSERT INTO dados (key1, valor) VALUES (" . ($i - 1) . ", " . ($i / 10) . ")";
        mysqli_query($db, $sql) or die(mysqli_error($db) . "\nFalha ao inserir registro na tabela 'dados'");  
    }
}
?>

I do not know php, but the logic behind it is simple.

Ex: values in the vector - > 0.5, 0.8, 0.9, 1.0, 2.0, 2.5;

Let's say the desired value is 4.0.

Within a repeat structure, I will have the variable "sum".

The first time the repeat structure is executed, the maximum number is added so that the sum variable does not exceed 4.0 (2.5).

At this point, sum = 2.5

The next execution of the repeat structure will add 1.0, because if you add 2.0 or 2.5 the value will exceed 4.0.

At this point, sum = 3.5

The next execution will add the value 0.5, since it is the largest value that when added to the variable "sum" will not cause the value to "pop".

At that point, sum = 4.0

Desired value reached.

I thought about the following:

$dados = array('0.10', '0.20', '0.30', '0.50',
                   '3.00', '3.30', '4.00', '5.00',
                   '1.00', '1.10', '2.00', '2.20');
    $valorX = 5.00;
    $nc = count($dados);

    for($a = 0; $a < $nc; $a++){
        for($b = 0; $b < $nc; $b++){
           if ( $a < $nc) {
                // verifica se os valores escolhidos somados são iguais ao valor escolhido
                if ($dados[$a] + $dados[$b] == $valorX) {
                    echo 'valor 1 = ' . $dados[$a] . ' / valor 2 = ' . $dados[$b] . '<br>';
                }
            } 
        }
    }