Move History

Fork Selected
  • Description

    We have n different groups of elements and we want to know all the possible combinations of n elements from these groups. Each combinations should be formed having one element from each group. The function generates all the possible different combinations.

    Code
    function groupCombinations_() {
        var r = [], arg = arguments, max = arg.length-1;
        function helper(arr, i) {
            for (var j=0, l=arg[i].length; j<l; j++) {
                var a = arr.slice(0); 
                a.push(arg[i][j]);
                if (i==max)
                    r.push(a);
                else
                    helper(a, i+1);
            }
        }
        helper([], 0);
        return r;
    }
    
    function groupCombinations(arr2D) {
        var combL = groupCombinations_.apply(this, arr2D);
        return [combL.length, combL];
    }
    Test Cases
    function groupCombinations_() {
        var r = [], arg = arguments, max = arg.length-1;
        function helper(arr, i) {
            for (var j=0, l=arg[i].length; j<l; j++) {
                var a = arr.slice(0); 
                a.push(arg[i][j]);
                if (i==max)
                    r.push(a);
                else
                    helper(a, i+1);
            }
        }
        helper([], 0);
        return r;
    }
    
    function groupCombinationsCheck(arr2D) {
        var combL = groupCombinations_.apply(this, arr2D);
        return [combL.length, combL];
    }
    
    
    
    describe("Basic Tests", function(){
      it("Simple Cases", function(){
        var arr2D = [[1,2,3,4], [1,2,3,4,5,6]];
        Test.assertSimilar(groupCombinations(arr2D), [24, [[1, 1], [1, 2], [1, 3], [1, 4],
        [1, 5], [1, 6], [2, 1], [2, 2],[2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], 
        [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4],[4, 5], [4, 6]]]);
        
        arr2D = [[1,2,3,4,5,6], [1,2,3,4,5,6]]; 
        Test.assertSimilar(groupCombinations(arr2D), [36, [[1, 1], [1, 2], [1, 3], [1, 4],
        [1, 5], [1, 6], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [3, 1], [3, 2], 
        [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], 
        [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 1], [6, 2], [6, 3], [6, 4],
        [6, 5], [6, 6]]]);
      });
    });
    
    function range(start, stop){
        var a=[start], b=start;
        while(b<stop){b++;a.push(b)}
        return a;
    }
    
    function randint(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    }
    
    function choice(items) {
        var item = items[Math.floor(Math.random()*items.length)];
        return item;
    }
    
    describe("Random Tests", function(){
      it("Challenging Cases", function(){
        var ranges = [range(1, 4), range(1,6), range(1,8), range(1,10), range(1,12), range(1,20)];
        for (var h = 1; h <= 20 ; h ++) {
            var n = randint(2, 3);
            var arr2D = [];
            while (true){
                arr2D.push(choice(ranges))
                if (arr2D.length == n) break;
            }
            var result = groupCombinationsCheck(arr2D);
            var res = groupCombinations(arr2D);
            it("Testing for arr2D = " + arr2D.toString(), function(){
              Test.assertSimilar(res, result);
            })
        }
      })
    })