Info

I am trying to find the amount of possible combinations of an array with 7 or 19 values.

Starting point with 7 values [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0];

Starting point with 19 values [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0];

There are 10 possible values each position in the array can have: 0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5

• Rule 1: The first value (index 0) can be a maximum of 3.5
• Rule 2: The second value (index 1) can be a maximum of 4
• Rule 3: Two neighbor values can not have a difference of more than 2.5

Without the rules the answer would have just been 10⁷ for 7 values and 10¹⁹ for 19 values.

Rule 1 and 2 are also pretty easy to add to the calculation as we can just remove 2 possibilities for the first value and 1 for the second value.

7 values: 8 * 9 * 10⁵ = 7200000

19 values: 8 * 9 * 10¹⁷ = 7200000000000000000

Problem

The problem for me is how to calculate the amount of combinations possible with rule 3 considered.

I have tried a couple of iterative solutions and some recursive solutions that runs through each combination and add to a counter if it is valid according to the rules, but quickly figured out it would take way to long for it to finish as it would have to run 10¹⁹ iterations for 19 values which would take years.

How can I calculate the amount of possible combinations with all 3 rules considered in a reasonable time.

Code

Here is the code I currently have which implements rule 1 and 2.

Note that I have used the npm module bignumbers.js to avoid rounding errors on big numbers.

const BigNumber = require("bignumber.js");

const findCombinations = (n) => {
    let totalCombinations = BigNumber(1);

    for (let i = 1; i <= n; i  ) {
        if (i === n) {
            totalCombinations = totalCombinations.times(8);
        } else if (i === n - 1) {
            totalCombinations = totalCombinations.times(9);
        } else {
            totalCombinations = totalCombinations.times(10);
        }
    }

    return totalCombinations;
};

console.log(findCombinations(7).toFixed());
console.log(findCombinations(19).toFixed());

CodePudding user response：

You can do this separately calculating the number of combinations that end in a certain symbol as you go.

function amount(init, step, len) {
  if (len < 1) return 0;
  const countsByRoundAndLastSymbol = [Object.fromEntries(init.map(symbol => [symbol, 1n]))];
  for (let i=1; i<len; i  ) {
    const prevCounts = countsByRoundAndLastSymbol[i-1]
    const counts = {};
    for (const [prevSymbol, prevCount] of Object.entries(prevCounts)) {
      for (const symbol of step(i, prevSymbol)) {
        counts[symbol] ??= 0n;
        counts[symbol]  = prevCount;
      }
    }
    countsByRoundAndLastSymbol[i] = counts;
  }
  return Object.values(countsByRoundAndLastSymbol[len-1]).reduce((sum, count) => sum   count, 0n);
}

Now you can apply your rules:

const possibleValues = [0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5];
for (const len of [7, 19]) {
  console.log(`Possible combinations of length ${len}:`, amount(
    possibleValues.filter(x => x <= 3.5),
    (i, prevSymbol) => possibleValues.filter(x =>
      Math.abs(x - prevSymbol) <= 2.5 &&
      (i != 1 || x <= 4)
    ),
    len
  ));
}