Transform results combination function into a dynamic function

Question

I have a function that generates all possible combinations of numbers from 1 to 10. The combinations are 4 numbers, that is, each combination has 4 different numbers. Ex:

[1,2,3,4], [1,2,3,5], [1,2,3,6] ... [7,8,9,10];

I can specify the range of possible numbers, which is currently 1 to 10.

My problem is that I cannot specify the amount of numbers that will make the combination. Which currently is 4 to another number.

I already broke my head to try to leave the dynamic function and only pass the parameters(in case it would be the range of numbers and the quantity of numbers of a combination), so:

GerarCombinacoes(10, 4); //onde 10 seria o range de numeros de 1 a 10 e 4 a quantidade de numeros da combinacao

My function is like this at the moment:

function GerarCombinacoes() {
    totalCombinacoes = 0;
    numeroMaximo = 10; //range de 1 a 10

    for (a = 1; a <= numeroMaximo ; a++) {
        for (b = 2; b <= numeroMaximo ; b++) {
            for (c = 3; c <= numeroMaximo ; c++) {
                for (d = 4; d <= numeroMaximo ; d++) {
                    if ((a != d && a != c && a != b)) {
                        if ((b != d && b != c && b != a) && b > a) {
                            if ((c != d && c != b && c != a) && c > b) {
                                if ((d != c && d != b && d != a) && d > c) {
                                    numeros = a + " - " + b + " - " + c + " - " + d;
                                    totalCombinacoes++;
                                    $("#Numeros").append("<p style='margin-left: 10px'>("+ totalCombinacoes+ ") " + numeros + "</p>");
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    alert(totalCombinacoes);
}  

If I want to increase the number amount of the combination I need to put one more go and one more check to not repeat numbers, but so it gets complicated because there are some cases I would need to do more than 20 is all in hand.

Answer 1

This is the kind of situation that a recursive solution would be more elegant than an iterative one. I’m going to suggest a very simple implementation, then refine it to make it more flexible and efficient:

function combinacoes(a, b, m, acc, retorno) {
    // acc são os elementos que já fazem parte da combinação
    if ( acc == undefined ) acc = []; // no início, ela começa vazia
    // retorno é a lista de combinações encontradas
    if ( retorno === undefined ) retorno = []; // idem
    if ( m == 0 ) {        // se o número de elementos a serem inseridos chegou a zero
        retorno.push(acc); // coloque a combinação atual na lista
        return retorno;    // e retorne
    }
    if ( a > b )           // se a passou b, não existem mais combinações
        return retorno;    // retorne o que foi achado anteriormente

    // Primeiro fazemos todas as combinações que incluem a
    // i.e. combinamos a com as combinações de tamanho m-1
    combinacoes(a+1, b, m-1, acc.concat([a]), retorno);

    // Depois todas as que não incluem a
    // i.e. ignoramos a, e fazemos as combinações de a+1 pra frente
    return combinacoes(a+1, b, m, acc, retorno);
}

Example in jsFiddle. The fact that the solution is recursive has no impact on efficiency, because the number of combinations of n elements m a m is so large (you’ve heard the expression "combinatorial explosion"?) that long before you have problems of stack overflow you will have memory loss problems....

Now I’m gonna refine it a little so it doesn’t spawn all combinations at once; instead, I will create a "pagination system" where the function only generates a small subset of the results at a time:

// Função auxiliar: quantas combinações existem de n elementos m a m?
// n! / (m! * (n-m)!)
function quantas(n, m) {
    m = ( m < n - m ? m : n - m ); // Para facilitar o cálculo... (pois é simétrico)
    var dividendo = 1;
    var divisor = 1;
    for ( var i = 2 ; i <= n ; i++ ) {
        if ( i <= m )
            divisor *= i;
        if ( n-m < i )
            dividendo *= i;
    }
    return dividendo / divisor;
}

function combinacoes(a, b, m, inicio, fim, acc, retorno) {
    if ( inicio === undefined ) inicio = 0;
    if ( fim === undefined ) fim = quantas(b-a+1, m);
    if ( fim <= 0 )
        return retorno;
    ...
    // Primeiro fazemos todas as combinações que incluem a
    if ( inicio < quantas(b-a, m-1) )
        combinacoes(a+1, b, m-1, inicio, fim, acc.concat([a]), retorno);
    // Depois todas as que não incluem a
    inicio -= quantas(b-a, m-1);
    fim -= quantas(b-a, m-1);
    return combinacoes(a+1, b, m, inicio, fim, acc, retorno);
}

Example in jsFiddle. Experiment with a "big nonsense" number, such as combinations 1 to 1000, 100 to 100. (Note: There are 6.38 10 139 results - bigger than it fits in a double - so the above method will "skip" some results... but most of them will come right)

Answer 2

Forget, for a moment, that we are talking about combinations of numbers.

Let’s say we have N elements, and that I want to calculate how many possibilities of combinations containing M elements are possible.

This is simply binary calculus.

I can ask myself another way: In N bits, I want all numbers with M connected bits.

The function to generate all binary maps of the combinations would look like this:

function GenerateCombinations(totalElements, elementCount) {

    console.debug('Total de elementos: ' + totalElements);
    console.debug('Elementos por combinação: ' + elementCount);

    var res = [];

    for (i = 0; i < Math.pow(2, totalElements); i++) { 

        var probe = i.toString(2).replace(new RegExp('0', 'g'), '');

        if(probe.length == elementCount)
            res.push(i);
    }    

    console.debug(res.length + ' combinações encontradas.');

    return res;
}

And finally, the function that performs the combination of elements:

function CombineElements(collection, elementCount) {
    var combinations = GenerateCombinations(collection.length, elementCount);

    var res = [];

    for(i = 0; i < combinations.length; i++) {

        bitmapIndex = combinations[i].toString(2).split("").reverse().join("");
        console.debug(i + ':' + bitmapIndex);
        var arItem = '';

        for(j = 0; j < bitmapIndex.length + 1; j++)
        {
            if (bitmapIndex.substring(j,j+1) == '1')
                arItem += collection[j];
        }

        res.push(arItem);
    }
    return res;
}

Some examples:

Collections of 2 items between 4 elements:

CombineElements([1,2,3,4], 2)

Total de elementos: 4  
Elementos por combinação: 2  
6 combinações encontradas.  
["12", "13", "23", "14", "24", "34"] 

Collections of 3 items between 6 elements:

CombineElements([1,2,3,4,5,6], 3)

Total de elementos: 6
Elementos por combinação: 3
20 combinações encontradas.
["123", "124", "134", "234", "125", "135", "235", "145", "245", "345", "126", "136", "236", "146", "246", "346", "156", "256", "356", "456"]

Code in the Jsfiddle.

Answer 3

Follows a combination function that allows you to use an array as data input:

function combinations( inpSet, qty ) {
  var inpLen = inpSet.length;
  var combi = [];
  var result = []; 
  var recurse = function( left, right ) {
    if ( right == 0 ) {
      result.push( combi.slice(0) );
    } else {
      for ( var i = left; i <= inpLen - right; i++ ) {
        combi.push( inpSet[i] );
        recurse( i + 1, right - 1 );
        combi.pop();
      }
    }
  }
  recurse( 0, qty );
  return result;
}

// Teste:
document.body.innerHTML += JSON.stringify(
  combinations( ['a','b','c','d'] , 3 )
);

This way, you can exchange the entry for the values you want.

Answer 4

I do not know JS, but I will explain a solution and show in C++, should not be difficult to translate.

One caveat: this type of algorithm has a disgusting complexity and soon stops working. For something less, Voce can try some of the solutions from here.

The algorithm works like this:

1. First we need a structure to store the permutations. In my case it will be a set, a C++ structure that allows you to store a single copy of each element in it (as a set of mathematics).
2. We’ll need another one too set to guard the combinacao atual that we are generating.
3. Now for the algorithm itself:
   1. We’re going to have a recursive function that works like this: for each element x from the list of 1 to your limit N, she tries to insert x in a cluster that is storing the combination up to here. If it can place x (what may not happen, since x can already be in the combination), it sees if the total size of the set is equal to the number of elements that Voce wants in the combination.
   2. If the size of the set is equal, store it in the array of combinations. If it is not, call the same function with the set with the new element.
   3. When the recursive call comes back, remove the element you placed from the set (in this case x).

When this thing is over, Voce will have all the combinations in the vector.

The code in C++:

#include <iostream>
#include <set>
using namespace std;

set< set<int> > combinacoes;

void gen(int limite, unsigned qtos, set<int>& ate_aqui) {
    for (int i = 1; i <= limite; ++i) {
    auto it = ate_aqui.insert(i);
    if (it.second == false) continue;
    if (ate_aqui.size() == qtos)
        combinacoes.insert(ate_aqui);
    else
        gen(limite, qtos, ate_aqui);
    ate_aqui.erase(ate_aqui.find(i));
    }
}

int main() {
    set<int> v;
    gen(4, 3, v);
    for (auto &c : combinacoes) {
        for (auto &x : c) cout << x << ' ';
        cout << endl;
    }
    return 0;
}

When I spin it to you gen(4, 3, v), that is, all combinations from 1 to 4 with 3 elements, the output is:

1 2 3 
1 2 4 
1 3 4 
2 3 4 

I do not know if it helps, but if not someone already put something more specific to JS.

Answer 5

To generate all possible combinations, including repeated numbers, use the section below. The parameter gama denotes the number of options for each cell (ie each cell will be filled with a value of 1 a gama). Already tamanho represents the length of each row of the resulting array, i.e., how many numbers from 1 to gama should be added to the array.

function GerarCombinacoes(gama, tamanho){
    var arr = [];
    for(var i = 0; i < Math.pow(gama, tamanho); i++){
        arr[i] = [];
        for(var j = 0; j < tamanho; j++){
            arr[i].push(Math.floor(i / Math.pow(gama, tamanho - j - 1)) % gama + 1);
        }
        arr[i] = arr[i].sort();
    }
    arr = arr.sort();

Note that the sort() show the same lines, as they organize the array vertically and horizontally. Add a filter to the resulting array to exclude all lines that have repeated elements or are equal to the top row (which, after the sort(), ensures that there will only be single lines).

    arr = arr.filter(function(linha, ind, array){
        var igual_linha_acima = true;
        for(var i = 0; i < linha.length; i++){
            for(var j = 0; j < linha.length; j++){
                if(i != j && linha[i] == linha[j]) return false;
            }
            if(linha[i] != array[ind-1][i]) igual_linha_acima = false;
        }
        if(igual_linha_acima) return false;
        return true;
    });

Finally, just return the resulting array of combinations.

    return arr;
}

Any questions, just ask that I detain more :)

Edit: I edited the answer to ensure single lines, and I also prepared a Jsfiddle.

Answer 6

Opps, 3 years late! a functional version in Python but easily javascriptable:

def p(comp,max,pref=[],min=1):
   if comp==0 :
      print(pref)
   else:
      for x in range(min, max-comp+2):
         p(comp-1, max, pref+[x], x+1)

p(3,4)