CODEWITHSUNDEEP
javascriptarraysalgorithm
Frederik Jorgensen
Frederik Jorgensen

Reputation: 358

3-Coloring of N-nodes

I'm trying to write a function that colors n nodes with all possible combinations of 3 colors.

Colors are stored in an array:

["red", "green", "blue"]

We represent nodes in an array.

Sample input:

[1,2]

Expected output:

[
  ["red", "red"],
  ["red", "green"],
  ["red", "blue"],
  ["green", "red"],
  ["green", "green"],
  ["green", "blue"],
  ["blue", "red"],
  ["blue", "green"],
  ["blue", "blue"]
]

The actual contents in the nodes array doesn't matter. The length of the array is the only thing that matters. So if it was a node array [1,2,3] the colors would be ["red","red","red"] etc...

This is my try so far.. I'm not sure how I can get the combination of every color?

const colors = ["red", "green", "blue"];
const newStates = [];

function allColors(nodes) {
  for (let i = 0; i < colors.length; i++) {
  const newState = [];
    for (let j = 0; j < nodes.length; j++) {
      newState.push(colors[i]);
    }
    newStates.push(newState)
  }
  return newStates;
}

const nodes = [1, 2];
console.log(allColors(nodes));

Upvotes: 1

Views: 46

Answers (1)

Patrick87
Patrick87

Reputation: 28302

If the array length is n and the number of colors is m, there are going to be m^n possible n-tuples of m colors. As suggested in comments, counting from 0 to m^n - 1 and converting to a base-m number is a good solution:

const colors = ["red", "green", "blue"];
const newStates = [];

function allColors(nodes) {
  for (let i = 0; i < Math.pow(colors.length, nodes.length); i++) {
   const newState = [];
    var curNum = i;
    for (let j = nodes.length - 1; j >= 0; j--) {
      var curPow = Math.pow(colors.length, j);
      newState.push(colors[Math.floor(curNum / curPow)]);
      curNum %= curPow;
    }
    newStates.push(newState)
  }
  return newStates;
}

Another option is something recursive:

function allColors(nodes) {
    var newState = [];
    allColorsInternal(nodes, curNode, 0);
}

function allColorsInternal(nodes, curNode, start) {
    if (start == nodes.length) {
        newStates.push(newState);
        return;
    }
    for (let i = 0; i < colors.length; i++) {
        curNode[start] = colors[i];
        allColorsInternal(nodes, curNode, start + 1);
    }
}

I haven't run either of these so they'll probably need a little cleaning up and debugging but the ideas will both work. The first constructs the entries iteratively by going through each one in base-m order; the second one does it by assigning the first position every possible color, and then recursively solving the subproblem of size n-1 for all positions to the right.

Upvotes: 2

Related Questions