# 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

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];
"1": {}
};
for (var i = 0; i < ar.length; 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;
}
}
}
}
``````

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