javascript - 所有行和列总和相等的二维 4x4 数组

绝对不是最快的方法，但它可能有用。
产生 549504 个变体大约需要 200 秒。
const startTime = Date.now();
const inputArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31];
const target = 64;

const combinationsOfFour = {};

//==================================================================
/*
  Section.1
  Find all valid combinations of four values from
  the input array that total the target.
  Store each combination in a nested object
  grouped by the first value in the combination,
  and referenced by a comma separated string of
  the combination.

  eg
  look_up_table = {
    1: {
      '1,2,3,4': [1, 2, 3, 4],
      '1,2,4,3': [1, 2, 4, 3],
      ...
    },
    2: {
      ...
    }
  }
*/

// --------------------------------------------

/*
  Take groups of four ascending values, and find all
  individual combinations, and assign them to their
  corresponding group in the lookup table,
  referenced by the comma separated string of their values
  eg
  abcd => 'a,b,c,d', 'a,b,d,c', 'a,c,b,d', 'a,c,d,b'...
*/
const assignAllVariants = groupA => {
  groupA.forEach((valA, indexA) => {
    const groupB = [...groupA];
    groupB.splice(indexA, 1);

    groupB.forEach((valB, indexB) => {
      const groupC = [...groupB];
      groupC.splice(indexB, 1);

      groupC.forEach((valC, indexC) => {
        const groupD = [...groupC];
        groupD.splice(indexC, 1);

        const valD = groupD[0];

        const combination = [valA, valB, valC, valD];
        combinationsOfFour[valA][combination.join(",")] = combination;
      });
    });
  });
};

// ----------------------------------------------

/*
  Get each combination of four ascending values that total the target

  * Note -  the input array would need an initial sort in cases where
          it is not already in ascending order.

    - loop through each value in the input array
      - assign that value to 'first'
      - beginning with the following value,
        loop through each value in the array
        - assign that value to 'second'
        - beginning with the following value,
          loop through each value in the array
          - assign that value to 'third'

          - subtract the sum of first, second and third
            from the target
          - assign this value to 'fourth'

          - check that fourth is greater than third,
            and less than or equal to the last value
            in the array.

            * Note if the input array is comprised of values with
              some other spacing eg(1, 3, 6, 10, 15...)
              then the value of 'fourth' would need to checked
              against the array for validity

          - All valid groups of four are passed to the
            function assignAllVariants
*/
const createGroup = (target, values) => {
  let first, second, third, fourth;

  values.forEach(val => (combinationsOfFour[val] = {}));

  return values.forEach((value, index) => {
    first = value;

    for (let i = index + 1; i < values.length - 2; i++) {
      second = values[i];

      for (let j = i + 1; j < values.length - 1; j++) {
        third = values[j];
        fourth = target - first - second - third;

        if (fourth <= third) {
          break;
        }

        if (fourth <= values[values.length - 1]) {
          const group = [first, second, third, fourth];
          assignAllVariants(group);
        }
      }
    }
  });
};

// ======================================================
/*
  Section.2
    - Loop through the values in the combinations table
      created in section 1.
      - Set the given combination to the first row of the grid.
      - Remove the values of that combination from a lookup table
        created from the input array.
      - Taking the value in the first position of the first row,
      - loop through the corresponding group in the combinations table
        - Check that the combination does not contain values already removed
          from the lookup table, or collide with existing values in the grid.
        - Apply this combination to the first column of the grid.
        - Repeat this process with the 2nd row, 2nd column, 3rd row...

        - If the fourth row is successfully assigned then add that completed
          grid to validLayouts

*/

const getGrid = (inputArray, combinations) => {
  let grid = [[], [], [], []];
  const validLayouts = [];

  const gridToString = grid => {
    return grid.map(row => row.join(",")).join("|");
  };

  // Check given combination against a lookup table of used/ unused values
  const checkLookup = (combination, start, lookUp) => {
    if (start > 0) {
      for (let i = start; i < 4; i++) {
        if (!lookUp[combination[i]]) {
          return false;
        }
      }
      return true;
    } else {
      return true;
    }
  };

  // Check given combination against existing values in the grid
  const checkAgainstGrid = (combination, n, axis) => {
    if (axis === "x") {
      if (n > 0) {
        for (let i = 4 - n + 1; i < 4; i++) {
          if (combination[4 - i] !== grid[n][4 - i]) {
            return false;
          }
        }
        return true;
      } else {
        return true;
      }
    } else if (axis === "y") {
      for (let i = 4 - n; i < 4; i++) {
        if (combination[4 - i] !== grid[4 - i][n]) {
          return false;
        }
      }
      return true;
    }
  };

  // Update lookup table
  const removeUsedValues = (combination, n, lookUp) => {
    const newLookUp = { ...lookUp };
    for (let i = n; i < 4; i++) {
      newLookUp[combination[i]] = false;
    }
    return newLookUp;
  };

  // -----------------------------------
  /*
    Only needed when examining failed grid attempts,
    can be removed, but minimal performance impact
    on the given set.
  */
  // Use to clear grid after unsuccessful branch
  const cleanUpGrid = (n, axis) => {
    if (axis == "x") {
      grid[n].splice(n);
    } else if (axis == "y") {
      for (let i = n + 1; i < 4; i++) {
        grid[i].splice(n);
      }
    }
  };
  // ------------------------------------------------

  // Assign passing combinations to the corresponding grid column
  const assignCol = (combination, n, lookUp) => {
    let newLookUp;
    // Check combination against lookup table and current grid values
    if (
      checkLookup(combination, n + 1, lookUp) &&
      checkAgainstGrid(combination, n, "y")
    ) {
      // remove used digits from lookup table
      newLookUp = removeUsedValues(combination, n, lookUp);

      // assign combination to column
      for (let i = n + 1; i < 4; i++) {
        grid[i][n] = combination[i];
      }

      Object.keys(combinations[grid[n + 1][0]]).forEach(ref => {
        const combination = combinations[grid[n + 1][0]][ref];

        assignRow(combination, n + 1, newLookUp);
      });

      cleanUpGrid(n, "y");
    }
  };

  // Assign passing combinations to the corresponding grid row
  const assignRow = (combination, n, lookUp) => {
    // Check combination against lookup table and current grid values
    let newLookUp;
    if (
      checkLookup(combination, n, lookUp) &&
      checkAgainstGrid(combination, n, "x")
    ) {
      // remove used digits from lookup table
      newLookUp = removeUsedValues(combination, n, lookUp);

      // assign combination to row
      grid[n] = [...combination];

      if (n === 3) {
        validLayouts.push(gridToString(grid));
      } else {
        Object.keys(combinations[grid[0][n]]).forEach(ref => {
          const combination = combinations[grid[0][n]][ref];

          assignCol(combination, n, newLookUp);
        });

        cleanUpGrid(n, "x");
      }
    }
  };

  // create initial lookup table from input array
  const lookUp = {};
  inputArray.forEach(val => (lookUp[val] = true));

  // main outer loop
  Object.keys(combinations).forEach(group => {
    Object.keys(combinations[group]).forEach(ref => {
      const combination = combinations[group][ref];

      assignRow(combination, 0, lookUp);
    });
  });
  return validLayouts;
};

//-------------------------------------------------------

createGroup(target, inputArray);
const validGrids = getGrid(inputArray, combinationsOfFour);

console.log(validGrids.length);
console.log(`Duration: ${(Date.now() - startTime) / 1000}s`);
javascript - 所有行和列总和相等的二维 4x4 数组

问题描述

解决方案

推荐阅读
