Cross values in array

Asked

Viewed 653 times

6

I have a value X and I have a array with various values.

I would like to search all the same values and smaller, which would enter into a combination that their sum would give the value X.

Example:

Array (in real scenario, thousands of values):

$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');

Assuming the value of X is 0.50, the possible sums would be:

  • 0.20 + 0.30
  • 0.50

Assuming the value of X is 1.10, the possible sums would be:

  • 0.10 + 0.20 + 0.30 + 0.50
  • 0.10 + 1.00
  • 1.10

Assuming the value of X is 1.40, the possible sums would be:

  • 0.10 + 0.30 + 1.00
  • 0.10 + 0.20 + 1.10
  • 0.30 + 1.10

What I’d like to know, are ways of performing this crossing, preferably with native functions.

I already have my ideas on how to do it, but if I post it, it can "addict" the idea of you, and end up going the same way I’m thinking, and if I’m wrong, I get in the way.

php logic

  • Just to confirm, although your example shows only 2 values per sum, the combination may involve ANY amount of elements, right? Ex: if the value X is 2.10, the elements could be for example 0+10 + 0.20 + 0.30 + 0.50 + 1.00 = 2.10 or 1.00 + 1.10 = 2.10 or 0.10 + 2.00 = 2.10, etc.?

  • @Rogériodec exactly! I will have a lines with thousands of values! I added 1 more example.

  • I’m trying to understand, it would be to add all the smaller values into one, or add one to one of these smaller ones with the X?

  • Would be all possible sum combinations, which would give the value of X.

  • For thousands of values I do not think it is possible to get all combinations, because if there are a thousand values the possible combinations are 1000!. But for something not too big you can do thus

  • @Isac did not understand your code, it does not have the reference value for the sums. And I also did not understand "because if there are a thousand values the possible combinations are 1000"... Possible combinations would start with values smaller than X, since the maximum value is X. With these values, you would have to test all possible combinations that give exactly the value of X.

  • Theoretically I would take 1 by 1, add it up in an ordered sequence, until it reaches the value of X or if it exceeds, the combination is no longer valid. Then it starts again, 1 by 1 and skips the value of the sequence, and continues to add the next ones, until see if it gives the value of X. So sequentially until testing all the possibilities of sum that will give X. Yes, it would be millions of calculations.

  • "if there are a thousand values the possible combinations are 1000!" (a thousand factorial) Do it in the calculator to see the number we are talking about. These are all the combinations that need to be analyzed to see if they give the sum you want. Of course many of them can be cut without being fully analyzed, but it’s still a lot. The reference value for the sum is passed in the function combinacoesParaObjetivo as the second parameter (in the example 1.1)

  • Wouldn’t they be more? Why do we count at the beginning of the array: I start by adding up the value of the array[0], array[1], array[2],...... if it doesn’t equal X, then it would start again array[0], array[2], array[3],...... really would be MANY "tests"...

  • The idea is this: I have for example 10,000 notes, and at their value, I need to find all that have the value of 100,51, or all combinations of values less, that the sum is equal to 100,51.

  • I don’t think you’re visualizing how much it is 1000! Has here on this page just for the fun :D. So yes have a "few" combinations to test

  • Now I get it! hahaha... this "!" is purposeful! I didn’t even know what that meant! rs Dude, so there is no such possibility ?

  • then just so you can understand better, you want to return a vector only with the combinations added to the past value? In a simpler example, A = 100; B = [...valores]; X = [A + B[0], A + B[1], A + B[2]];, of course the X array would be generated by the algorithm, but idea is to understand if I understood your need

  • That’s it. It’s just that printing or returning in array doesn’t matter, because I’ll have other manipulations later. But yes, it would be all possible combinations that the sum gives X. Like in the examples I gave, the return will have to contain what are the combinations of the values of the array, which summed give X.

  • For everyone who wants to discuss the question, I’ve created a chat

Show 10 more comments

4 answers

2


It took me eight hours to develop the algorithm, but thanks for 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 a value to be compared, 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 in https://ideone.com/BCyi6v#stdin

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

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

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

  • Caraca bicho! Sensational! I will look with LOTS of calm, try to understand and ask the points that do not understand. I’m sure I’ll have questions, so I’ll start a chat.

  • chat

  • Did it work? If yes, please approve the answer and positive.

  • Roger hasn’t finished testing... considering yes... just bring the same number too...

  • "bring the equal number", you want to compare a simple number of the array with the number you are testing? Ex: if in the array you have 1.20, 3.90, 4.70 and you are searching for example 3.90 it should also charge, that? But this is simple, just add a code by doing a 1 to 1 comparison before.

  • Yes... I haven’t had time to pick it up yet. As there is a limit because of comparisons, so I won’t even be able to use it. But it was nice the "challenge". Thank you!

  • Sorry, but which limit?

  • I put an array with 60 values, the last combination he gets is : 889, and gives memory error Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes) in C:\xampp\htdocs\_test\cruzaarray.php on line 55. As in my case can reach thousands of records and 80 already depletes the memory, so no conditions. It would have to be a different logic, which I believe you don’t have because of the combinations, correct!?

  • 1

    I made the code thinking about minimizing memory consumption. It can decrease a little more by removing the array $dadosf[] and replacing his references with floatval($dados[..., but that won’t solve the problem for so many combinations. In this post (https://stackoverflow.com/questions/561066/fatal-error-allowed-memory-size-of-134217728-bytes-exhausted-codeigniter-xml) there are references to increasing the memory limit of PHP depending on the server you use. But I think the ideal in this case would be to use a disk cache.

  • Yes, in memory there is no way, so I gave up. But now use disk cache, I had never heard it. I’ll give a search! Thank you very much!

  • I am happy at least to know that logic works, so the challenge (much less) now is to make it fit in the memory. When I talk about caching, it is not something native to php, I mean reading and recording the arrays on disk, I mean, tampering with the code in the most critical areas and read on disk instead of leaving everything in RAM.

  • Let’s go continue this discussion in chat.

  • Oops, I sent a question on chat, you got the warning?

Show 8 more comments

1

EDITION:

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

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

1]

So, if the array $dados for example only 30 items items, the number of possible combinations would be 2^30 - 1 = 1.073.741.823; if 100 items = 1,26765E+30!!!

One can also calculate how many combinations are possible per level, that is, combination with 2 numbers together, 3 numbers, etc. In this case the formula is:

2]

... 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 question: 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 recreated the entire algorithm so that large arrays are used in database tables.

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

It is worth noting that although this second approach solves the problem of RAM bursting, the counterpart is that it will become absurdly slower. I mean, if you’re going 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 on this link: http://sandbox.sortemaniasudoeste.com.br/wp-content/php/comb.php

In short, to function, it is enough:

  1. Create a Mysql database (empty)
  2. Modify database data in source code
  3. Modify the value to be tested and the number of elements (this part you will replace with your original table)

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'");  
    }
}
?>

  • Phenomenal guy! Awesome! I answered you in the chat room!

  • 1

    I created a revision in the code, as the mysqli_query loads all data from the table in RAM, a previous excerpt with SELECT * FROM base was giving out memory when the table base reached a few million records. I believe that this way is now better. I also think we can improve the performance issue, but this requires a deeper study. The important thing is that now works without limit of items.

  • It would have a way of calculating the expected completion time?

  • 1

    It should, but this should be done based on a mathematical study of combinatorial analysis, based on the current algorithm, in addition to analyzing the response time between communications with the bank, which are variables. But I imagine that depending on the amount of items to be analyzed and consequently the amount of combinations, it can take days or weeks... yet it is faster than if it were done 'in the hand', rsrsrs.

  • 1

    The formula to know how many combinations are possible within "x" items is: 2^x - 1. For example, if $dados has 30 items, then 2 30 - 1 = 1,073,741,823 possible combinations!

  • Dude, it’s a processing sprout! Very raw!

  • I would say that depending on the number of items, this would be unviable. For example, for 1000 items, I would give 1,0715E+301 of combinations... I think there aren’t even as many atoms in the universe, rsrsrs.

  • That’s what Isac said in the comments, and passed that link Factorial 1000 aburdo! hahaha

  • While perhaps all this work will turn out to be unworkable, I still left an issue in the reply to alert you to these conclusions, including formulas to get to the totals, should anyone in the future look for something similar. Still, thanks for the "challenge"!

Show 4 more comments

0

I don’t know php, but the logic behind it is simple.

One of the possible ways to do this is, within a repeating structure have a sum variable (e.g., sum), whose goal is to match the intended value (value reported by Voce) and, in the form of a loop, obtain from within the vector the greatest possible value that when summed in the control variable "sum" will not exceed the intended value. this will be executed until the sum variable equals the intended value or it exceeds the intended value.

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

Let’s say the intended value is 4.0.

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

The first time the repeating structure is executed, as many as possible will be added so that the sum variable does not exceed 4.0 (2.5).

At that point sum = 2,5

The next execution of the repeat structure will add 1.0, as if 2.0 or 2.5 is added the value will exceed 4.0.

At that point sum = 3,5

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

At that point sum = 4,0

Target value achieved.

  • Filipe, I did a test exactly on this logic, to keep adding. But it doesn’t work. If I add sequentially, I won’t have all the possible combinations. The thing is to actually cross-reference all the data, also in this idea of sum.

-3

I thought 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>';
                }
            } 
        }
    }

  • Dude, it’s full of bugs. You’ve managed to reproduce there?

  • I did, now you’re right.

  • Leandro, is not working. It can have more than 2 values, and should also bring all possible combinations. Check your script, try to reproduce the examples I posted. If knocking, then it worked! But thanks for the try :)

  • I redid the code (rs), and now it is checking all items in the array (just came to understand your goal now).

  • Right away I saw that it was wrong. You lock 2 values. Do as I said, test my examples, try to reproduce them, so you see if it is correct.

Browser other questions tagged php logic

You are not signed in. Login or sign up in order to post.