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;