Turn result combining function into a dynamic function

This is the kind of situation where a recursive solution would be more elegant than an iterative one. I'll suggest a very simple implementation, then refine it to become 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 since the number of combinations of n elements is so great (have you heard the expression "

Now I'm going to refine it a bit so I do not generate all combinations at once; instead, I'm going to create a "paging 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 an "absurdity of large" number, as combinations of 1 to 1000, 100 to 100. (Note: there are 6.38 × 10 ^ 139 results - greater than it fits in double - so the above method will" skip "some results ... but most of them will come right)

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

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

This is simply binary calculation.

I can ask myself in a different way: In% with% bits, I want all numbers with N bits attached.

The function to generate all the 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 among 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 among 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 JSFiddle.

Here is a combination function that allows you to use an array as 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 )
);

In this way, you can change the entry by the values you want.

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

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

The algorithm works like this:

When this thing is over, you 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 move this to gen(4, 3, v) , that is, all combinations of 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 has already posted something more specific to JS.

To generate all possible combinations, including repeated numbers, use the excerpt below. The gama parameter denotes the number of options for each cell (that is, each cell will be populated with a value of 1 to gama ). Since tamanho represents the length of each row of the resulting array, that is, how many numbers from 1 to gama must 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() shows the same rows, because they organize the array vertically and horizontally. Add a filter to the resulting array to exclude all rows that have repeating elements or that are equal to the top row (which, after sort() , ensures there will be only single rows).

    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 what I detail more:)

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

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

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)