Transform result combination function into a dynamic function

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 calculation.

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

The function to generate all the binary maps of the combinations would be 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 not JSFiddle.

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 input for the values you want.

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

One caveat: this type of algorithm has a disgusting complexity and soon stops working. For something less worse, you can try some of the solutions 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 will also need another set to save the combinacao atual we are generating.
3. now for the algorithm itself:
   1. we will have a recursive function that works like this: for each element x of the list that goes from 1 up to its limit N, it tries to insert x into a set that is storing the combination up to here. If she can put x (which 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 you want in the combination.
   2. if the set size is equal, store it in the combination vector. If not, call the same function with the set with the new element.
   3. when the recursive call returns, it removes from the set the element it placed (in the case x).

When this thing is over, you'll 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 trim this to gen(4, 3, v), i.e. 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 don't know if it helps, but if not someone already posts something more specific to JS.

To generate all possible combinations, including repeated numbers, use the excerpt below. The parameter gama denotes the number of options for each cell (that is, each cell will be filled with a value from 1 to gama). Already tamanho represents the length of each row of the resulting array, that is, 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 rows as they arrange the array vertically and horizontally. Add a filter to the resulting array to exclude all rows that have repeated elements or that are equal to the top row (which, after sort(), ensures that 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 combination array.

    return arr;
}

Any questions, just ask that I detail more :)

Edit: I edited the answer to ensure single rows, and I also prepared a jsfiddle .

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

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)