Algorithm to return all combinations of 3 combinations from a array of length 6 without the number appearing with the same set of numbers

Question

I was trying to write a algorithm in javascript that returns all the possible 3 digit numbers numbers from a given array of length 6 For Example

var arr = [1, 2, 3, 4, 5, 6];

I have already got the combinations with the same sets of numbers in different positions in the 2D array. (The code which I took the help of)

If I have the same numbers in different combinations then I would like to remove them form the array. like I have [1, 2, 3] at index i in the array comtaining all the possible combinations then I would like to remove other combination with the same numbers like [2, 1, 3], [1, 3, 2] and so on..

Note the array also contains numbers repeated like [3, 3, 3], [2, 2, 2], [3, 2, 3] and so on

I expect an 2d array which has the values : [[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,3,4]] and so on (24 possibilities)

Is there any way to do this?

Answer 1

Extending the answer you linked, just filter out the results with the help of a Set.

Sort an individual result, convert them into a String using join(), check if it's present in set or not, and if not, then store them in the final result.

function cartesian_product(xs, ys) {
  var result = [];
  for (var i = 0; i < xs.length; i++) {
    for (var j = 0; j < ys.length; j++) {
      // transform [ [1, 2], 3 ] => [ 1, 2, 3 ] and append it to result []
      result.push([].concat.apply([], [xs[i], ys[j]]));
    }
  }
  return result;
}

function cartesian_power(xs, n) {
  var result = xs;
  for (var i = 1; i < n; i++) {
    result = cartesian_product(result, xs)
  }
  return result;
}

function unique_cartesian_power(xs, n) {
  var result = cartesian_power(xs, n);
  var unique_result = [];
  const set = new Set();

  result.forEach(function(value) {
    var representation = value.sort().join(' ');
    if (!set.has(representation)) {
      set.add(representation);
      unique_result.push(value);
    }

  });

  return unique_result;
}


console.log(unique_cartesian_power([1, 2, 3, 4, 5, 6], 3));

Answer 2

const arr = [1, 2, 3, 4, 5, 6];

const result = arr.reduce((a, v) => arr.reduce((a, v2) => {
	arr.reduce((a, v3) => {
		const current = [v, v2, v3].sort().join(",");
		!a.find(_ => _.sort().join() === current) && a.push([v, v2, v3]);
		return a;
	}, a);
	return a;
}, a), []);

console.log(result.length);
console.log(...result.map(JSON.stringify));

Answer 3

You could take an iterative and recursive approach by sorting the index and a temporary array for the collected values.

Because of the nature of going upwards with the index, no duplicate set is created.

function getCombination(array, length) {
    function iter(index, right) {
        if (right.length === length) return result.push(right);
        if (index === array.length) return;
        for (let i = index, l = array.length - length + right.length + 1; i < l; i++) {
            iter(i + 1, [...right, array[i]]);
        }
    }
    var result = [];
    iter(0, []);
    return result;
}

var array = [1, 2, 3, 4, 5, 6],
    result = getCombination(array, 3);

console.log(result.length);
result.forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

This is a good example, that it is usually worthwhile not asking for a specific answer for a generic problem shown with a specific question; however as you've requested - if you really have the above constraints which kind of don't make much sense to me, you could do it like that:

function combine(firstDigits, secondDigits, thirdDigits) {

  let result = [];

  firstDigits.forEach(firstDigit => {
// combine with all secondDigitPermutations
secondDigits.forEach(secondDigit => {
  // combine with all thirdDigitPermutations
  thirdDigits.forEach(thirdDigit => {
    result.push([firstDigit, secondDigit, thirdDigit])
  })
})
  });

  // now we have all permutations and simply need to filter them
  // [1,2,3] is the same as [2,3,1]; so we need to sort them 
  // and check them for equality (by using a hash) and memoize them
  
  // [1,2,3] => '123'
  function hashCombination(combination) {
return combination.join('?_?');
  }

  return result
// sort individual combinations to make them equal
.map(combination => combination.sort())
.reduce((acc, currentCombination) => {
  // transform the currentCombination into a "hash"
  let hash = hashCombination(currentCombination); 
  // and look it up; if it is not there, add it to cache and result
  if (!(hash in acc.cache)) {
    acc.cache[hash] = true;
    acc.result.push(currentCombination);
  } 
  return acc;
  
}, {result: [], cache: {}})
.result;
}

console.log(combine([1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6]).length);
console.log(...combine([1,2,3,4,5,6],[1,2,3,4,5,6],[1,2,3,4,5,6]).map(JSON.stringify));

This does not include some super-clever assumptions about some index, but it does abuse the fact, that it's all about numbers. It is deliberately using no recursion, because this would easily explode, if the amount of combinations is going to be bigger and because recursion in itself is not very readable.

For a real world problem™ - you'd employ a somewhat similar strategy though; generating all combinations and then filter them. Doing both at the same time, is an exercise left for the astute reader. For finding combinations, that look different, but are considered to be the same you'd also use some kind of hashing and memoizing.

Answer 5

let arr1 = [1,2,3,4,5,6];

function getCombination(arr){
    let arr2 = [];
    for(let i=0; i<arr.length; i++){
        for(let j=i; j<arr.length; j++){
            for(let k=j; k<arr.length; k++){
                arr2.push([arr[i],arr[j],arr[k]]);
            }   
        }
    }
    return arr2;
}

console.log(getCombination(arr1));