Mathematical Combinator

6

I have a list of ex numbers:

[1, 2, 3, 4]

I need to know all the possible combinations of this list, remembering that the list can contain n elements, does anyone have any code examples or could you help me?

For this example list the expected result would be:

[1]
[2]
[3]
[4]
[1,2]
[1,3]
[1,4]
[1,4]
...
[1,2,3]
[1,2,4]
[1,3,4]
... e assim por diante.

Thank you.

    
asked by anonymous 01.10.2014 / 13:51

3 answers

3

Since you did not specify a language, I'll give you an example in Javascript:

var result = {};
function MeDaUmNumero(arr) {
    result[arr.join(", ")] = true;
    if (arr.length === 1) {
        return arr[0];
    }
    for (var i = 0; i < arr.length; i++) {
        var arrCopy = arr.slice(); // Isso copia o vetor em uma nova variável.
        arrCopy.splice(i, 1); // Isso remove o elemento no índice 'i'.
        MeDaUmNumero(arrCopy);
    }
}

You call the function by passing its vector. In the end, the variable result is a dictionary where the keys are the combinations (the values are all, arbitrarily, true - you can use another value). I'll leave the code analysis effort to you.

Q.: This algorithm delivers unordered combinations. For ordered combinations, simply rearrange the vector n! (factorial of n ) times, and for each iteration call the same function again.

Updating: I did an iterative rather than recursive version, for another answer . Follow here:

var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var resultado = {
    "1": {}
};
for (var i = 0; i < ar.length; i++) {
    resultado["1"][ar[i] + ""] = [ar[i]];
}

var tamanhoMaximo = ar.length;

for (var tamanho = 2; tamanho <= tamanhoMaximo; tamanho++) {
    var tamanhoAtual = resultado[tamanho + ""] = {};
    var tamanhoAnterior = resultado[(tamanho - 1) + ""];
    for (var chave in tamanhoAnterior) {
        var tempAr = tamanhoAnterior[chave];
        for (var i = 0; i < ar.length; i++) {
            if (tempAr.indexOf(ar[i]) == -1) {
                var novoAr = tempAr.slice();
                novoAr.push(ar[i]);
                novoAr.sort();
                tamanhoAtual[novoAr.join(",")] = novoAr;
            }
        }
    }
}
resultado;
    
01.10.2014 / 14:38
3

I'm going to use PHP as a base because of related question about sum of numbers .

If the sorting of the output does not have much problem, this one is well-efficient algorithm :

<?php
   $len = 10;
   for( $i = 1; $i < pow( 2, $len ); $i++ ) {
      for( $j = 0; $j < $len; $j++ ) {
         if( ( 1 << $j ) & $i ) echo $j + 1 . ' ';
      }
      echo "<br>\n";
   }
?>

See working at IDEONE .


If you need to sort the output, see a "trick" using arrays :.

<?php
   $len = 10;
   $output = array();
   for( $i = 1; $i < pow( 2, $len ); $i++ ) {
      $line = array();
      for( $j = 0; $j < $len; $j++ ) {
         if( ( 1 << $j ) & $i ) $line[] = $j + 1;
      }
      $output[count($line)][] = $line;
   }

   foreach( $output as $group ) {
      foreach( $group as $line ) {
         foreach( $line as $item ) echo "$item ";
         echo "<br>\n";
      }
   }
?>

See working at IDEONE .

    
02.10.2014 / 19:42
2

Thanks to those who contributed, based on the Renan algorithm I converted into php and managed to find what I expected, thank you very much.

$result = array();
MeDaUmNumero(array(1, 2, 3, 4), $result);
function MeDaUmNumero($arr, &$result) {
    if (!in_array(implode(',', $arr), $result)) {
        $result[] =  implode(',', $arr);
    }
    if (count($arr) === 1) {
        return $arr[0];
    }
    for ($i = 0; $i < count($arr); $i++) {
        $arrCopy = array_slice($arr, 0); // Isso copia o vetor em uma nova variável.
        array_splice($arrCopy, $i, 1); // Isso remove o elemento no índice 'i'.
        MeDaUmNumero($arrCopy, $result);
    }
}
    
01.10.2014 / 16:48