Finding all combinations in javascript

Question

I am creating a game and I need to generate some game pieces. Each piece is an array consisting of 4 numbers(each represents a property of the piece) ranging from 0-2. I need to generate all combinations to get all the game pieces.

So I would need [1, 0, 2, 0], [2, 0, 0, 1], [0, 0, 0, 0], [1, 0, 1, 0] etc..

There should be 81 total combinations of [a, b, c, d] where each variable is a number 0-2.

I am using javascript but any psudocode would be helpful.

Any help is appreciated. Thanks!

• user1046334: Those are not permutations. Permutations are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].
• Sergio Tulentsev: AFAIK, what you want is called combinations, not permutations.
• Hippocrates: Right, not combinations. That's what I have in my example correct?
• Lucero: Sounds like homework... tip: You can make 4 nested loops.
• katspaugh: If it were homework, they wouldn't be calling combinations permutations.

Answer 1

Mine

var arr=[];
for (var str,i=0;i<81;i++) {
 str = i.toString(3);
 arr.push(("000"+str).slice(-4)); // Hmm, I thought slice returned an array.
}

Here is an update taking into account the comments from @katspaugh and @herby

var arr=[];
for (var str,i=81;i<162;i++) {
 str = i.toString(3);
 arr.push((str).slice(-4).split('').map(Number));
}

• user1046334: toString(3)! I completely forgot!
• katspaugh: @herby, it's fortunate, because this toString/slice approach is 42% slower.
• user1046334: As for the slice, you can instead use Array's slice explicitly: [].slice.call("000"+str, 4). Also, if i would start with 81 and ended with < 162 /* 2*81 */ then "000"+str trick is not needed.
• user1046334: @katspaugh: Not to mention that it does not solve the problem correctly because it stores one-character strings, not Numbers (map(Number) would do the trick, but make it even slower).
• mplungjan: Did you measure how slow it was making 81 arrays? Also I think mine is easier to read than your generic ones

Answer 2

If it is a homework, tag it as such.

var BASE = 3, LEN = 4, LIMIT = Math.round(Math.pow(BASE, LEN));
var c = [];
for (var i = 0; i < LIMIT; ++i) {
 var item = [];
 for (var j = 0, k = i; j < LEN; ++j, k = Math.floor(k/BASE)) {
 item.push(k % BASE);
 }
 c.push(item);
}

Here is a more tricky solution but showing the math behind it better, hopefully:

var BASE = 3, LEN = 4;
var powers = [];
for (var i = 0, LIMIT = 1; i < LEN; ++i, LIMIT *= BASE) {
 powers.push(LIMIT);
}
var c = [];
for (i = 0; i < LIMIT; ++i) {
 c.push(powers.map(function(basePower) {
 return Math.floor(i/basePower) % BASE;
 }));
}

• user1046334: After seeing @katspaugh made generic solution, I'm gonna make mine generic as well...

Answer 3

var BASE = 3, COMB_LEN = 4
var max = parseInt(new Array(COMB_LEN + 1).join(BASE - 1), BASE),
 comb = new Array(COMB_LEN + 1).join(0).split('').map(Number)
var combinations = [], i, n
for (i = 0; i <= max; i++) {
 n = i.toString(BASE).split('').map(Number)
 combinations.push(
 comb.slice(0, COMB_LEN - n.length).concat(n)
 )
}

• user1046334: This, too, produces strings, not numbers, doesn't it?