Mathematical combinatorics

Question

I have a list of ex numbers:

[1, 2, 3, 4]

and I need to know all possible combinations of that list reminding me that the list may contain n elements, someone has some code or could 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.

Answer 1

I will use PHP as a base because of related question about number sum.

If the ordering of the output does not have much problem, this one is a very 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 on IDEONE.

If you need to sort the output, see a "ruse" 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 on IDEONE.

Answer 2

Since you didn’t specify 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. At the end, the variable result be 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.

P.S.: this algorithm delivers the 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 made an iterative version instead of recursive, to another answer. Follows 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;

Answer 3

Thanks those who contributed, based on Renan’s algorithm 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);
    }
}