How do I find all permutations from a series of arrays that act as rows and columns in javascript?

user_14852741 0
Viewed 78

Here is my example data structure:

r stands for row.

var data = {
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"]
}

How would I go about finding all of the paths where paths cannot be the same, paths can only traverse starting horizontally (and only starting in row 0), then vertically, then horizontally, etc., during a path it cannot pick the same value. Paths can "jump" values though, if a valid value is detected in the current row/column.

Rows and columns start at index 0.

Examples of expected paths output from future algorithm:

RowColumn(value),....

// these paths stop because there are no more valid vertical or horizontal values to pick.
00(E9), 10(1C), 11(E9), 01(55), 02(1C), 22(55), 12(E9)
02(1C), 22(55), 20(BD), 00(E9), 01(55), 21(1C), 11(E9), 10(1C), 12(E9)
permutation path arrays javascript
2 Answers

Rules used in this answer

When reading your question, I understood that the rules were:

  • start from 0_0
  • start by going horizontally
  • alternate horizontal/vertical on every move
  • never visit the same cell twice
  • we can jump over cells that have already been visited
  • the paths don't have to cover the entire grid

Algorithm

To get every path following these rules, you can use a recursive function (a function which calls itself).

In the following example, it takes 2 parameters:

  • path: an Array of visited cells
  • horizontal: a Boolean describing whether we should move horizontally or not

The first time we call it, we give it a path containing the first cell (['0_0']), and true because we have to move horizontally.

It would then:

  • find the cells in the same row or col as the last visited cell which have not yet been added to the path (horizontally or vertically depending on the current direction)
  • call itself for each of these nextCells, adding that cell to the path and switching direction

Code

function rowColumn(obj) {
  // Convert the Object to a 2D Array
  const data = Object.values(obj),
        rows = data.length,
        cols = data[0].length,
        res  = [];
  
  function recursive(path, horizontal) {    
    // Get the row or column cells that haven't been visited yet
    const nextCells = getNextCells(path, horizontal);
    
    // If no neighbors were found, push the result and return
    if (!nextCells.length) return res.push(path);
    
    // Apply recursion for all possible neighbors
    nextCells.forEach(cell => recursive(path.concat(cell), !horizontal));
  }
  
  function getNextCells(path, horizontal) {
    const [x, y] = path[path.length - 1].split('_').map(v => +v);
    let cells = [];
    
    if (horizontal) cells = Array.from({length: cols}, (_, i) => `${i}_${y}`);
    else            cells = Array.from({length: rows}, (_, i) => `${x}_${i}`);

    // Remove the cells that have already been visited
    return cells.filter(p => !path.includes(p));
  }
  
  // Start the recursion
  recursive(['0_0'], true);
  // Format the result
  return res.sort((a, b) => a.length - b.length)
            .map(path => path.map(cell => {
              const [x, y] = cell.split('_').map(v => +v);
              return `${x}${y}(${data[y][x]})`;
            }));
}

const data = {
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"],
};

const res = rowColumn(data);
console.log(
  `There are ${res.length} paths possible:`,
  res.map(path => path.join(' '))
);

user_19137290 

// Trying to replicate output 00(E9), 10(1C), 11(E9), 01(55), 02(1C), 12(E9), 22(55), 21(1C), 20(BD)

const algo = (values) => {
  // Find the number of keys of the values/data object
  const totalKeys = Object.keys(values).length

  // Cycle through the keys with an assumption that the first key is always 'r0'
  for (let row = 0; row < totalKeys; row++) {
    // construct a key name
    const keyName = "r" + row

    // get the array associated with this key
    const arr = values[keyName]

    // loop through the array
    for (let column = 0; column < arr.length; column++) {
      // get the current value
      const value = arr[column]

      // do whatever you want to do with values, I am just printing them here
      console.log("" + row + column + "(" + value + ")")
    }
  }
}

const data = { // usage of var is discouraged, use let or const instead
  r0: ["E9", "55", "1C"],
  r1: ["1C", "E9", "E9"],
  r2: ["BD", "1C", "55"]
}

algo(data);

user_98058670
Related