How to generate every possible combination of elements in array between range

Question

I'm using Javascript at the moment but open to anything. I want to generate every possible combination of elements of an array of size X where each element can only be N different values

For example I have an array size of X = 3, and different values of N = 2

001 011 111 100 110 000 010 101

I think that's all the combinations. I feel like this should be a common programming issue and a simple task but haven't been able to find anything that reflects what I need, most cases don't take into the account the possibility of multiple occurrences of the same number (e.g. 111)

Thats only returning a count, unless I'm missing something obvious. I want all the combinations. — The Empire Strikes Back, Dec 14 '18 at 23:47
Does this help: https://stackoverflow.com/questions/45347940/efficient-algorithm-to-get-the-combinations-of-all-items-in-object — haldo, Dec 14 '18 at 23:52
I believe what I'm looking for (after some research) is all possible permutations with repetition, though I can't seem to find a nice javascript snippet. — The Empire Strikes Back, Dec 14 '18 at 23:56

Purag · Answer 1 · 2018-12-15T00:19:38.113

You should frame this as a recursive problem: how do you generate combinations of length 3 for the alphabet [0, 1]? Well, you generate all the combinations of length 2, and for each string (call it s), generate two new results: 0s and 1s. Similarly for generating the combinations of length 2.

For the base case, for length 1, we can just return the alphabet itself.

Here's some JavaScript code:

function combine(alphabet, length) {
  if (length === 1) return alphabet;
  let combinations = [];
  for (s of combine(alphabet, length - 1))
    for (c of alphabet)
      combinations.push(c + s);
  return combinations;
}

Alternatively, if you want to support getting 0-length combinations, your base case could return a list containing only the empty string:

function combine(alphabet, length) {
  if (length === 0) return [""];
  let combinations = [];
  for (s of combine(alphabet, length - 1))
    for (c of alphabet)
      combinations.push(c + s);
  return combinations;
}

score 1 · Answer 2 · answered Dec 15 '18 at 00:03

This may be what you need:

function combinations(size, values) {
    var result = [];
    for (let k = 0; k < Math.pow(values, size); k++) {
        result.push(k.toString(values));
    }
    return result
}

What this does is count from 0 to (values^size)-1, while expressing all numbers in base values.

Combinations that start with one or more 0s are not padded. Pad them if you want to get 0011, 0101, etc.

Example:

For a size of 3 and 2 different values you'll get:

["0", "1", "10", "11", "100", "101", "110", "111"]

For a size 4 and 3 different values:

["0", "1", "2", "10", "11", "12", "20", "21", … ,"2202", "2210", "2211", "2212", "2220", "2221", "2222"]

score 0 · Answer 3 · answered Dec 14 '18 at 23:46

here's a code in c to help you:

// counter
#include <iostream>
using namespace std;
int main()
{
    int n,b,k;
    cin>>n>>b;
    int A[n+1];
    for(int i=0;i<=n;i++)
    {
        A[i]=0;    
    }
    while(A[n]!=1)
    {
        for(int i=(n-1);i>=0;i--)
        {
            cout<<A[i]<<"  ";
        }
        cout<<"\n";
        A[0]++;
        k=0;

    while(A[k]==b)
    {
        A[k]=0;
        A[k+1]++;
        k++;
    }
    }
    return 0;
}

It should be easy to figure it out, change it to java as a practice.

score 0 · Answer 4 · answered Dec 15 '18 at 00:21

A convenient way to deal with this is to pass the state in the parameters of the recursive function. Then you can simplify the backtracking and use some nice ES6 convenience to make the code short and readable:

function makeCombo(vals, n, current = [], res = []) {
  if (current.length == n) return res.push(current)           // stop if the current call is the target length
  vals.forEach(v => makeCombo(vals, n, [...current, v], res)) // other wise loop over values and recurse   
  return res
}


// binary counting:
console.log(makeCombo([0, 1], 3).map(a => a.join(',')))

// more values:
console.log(makeCombo(['a', 'b', 'c'], 3).map(a => a.join(',')))

How to generate every possible combination of elements in array between range

4 Answers4