关于改进计算方式

[zRains]

感谢开发者，已经获得了限定勋章😁。使用过程中我发现计算结果出现了多次重复，下面是测试用例：

let numbers = [1024, 1024, 1024, 11, 11, 34]
let symbols = [ '>>', '>>', '>>', '>>', '<<', '|']

计算代码中(快速计算)出现了比较多的嵌套循环结构和eval，比较影响效率。我参考了Heap's algorithm方法重写了排列组合方法，它不用花费额外的空间，并且执行效率蛮高的，并且做了去重处理：

/**
 * 重排列
 * @param {number[]} a
 * @param {number} [s]
 * @param {number[][]} [r]
 * @returns
 */
function pr(a, s = a.length, r = []) {
  const swap = (_a, _b) => ([a[_a], a[_b]] = [a[_b], a[_a]])
  if (s === 1) r.push([...a])
  for (let i = 0; i < s; i++) {
    pr(a, s - 1, r)
    s % 2 === 1 ? swap(0, s - 1) : swap(i, s - 1)
  }
  return r
}

/**
 * 重组合
 * @param {number[]} a
 * @param {number} k
 */
function co(a, k) {
  let result = [],
    path = []

  /**
   * 
   * @param {number[]} _a
   * @param {number} _k
   * @param {number} _i
   */
  const recur = (i) => {
    if (path.length === k) {
      result.push([...path])
      return
    }
    for (; i < a.length; i++) {
      path.push(a[i])
      recur(i + 1)
      path.pop()
    }
  }
  recur(0)
  return result
}

下面是benchmarkJS的测试比较两种计算代码：

// Solution_1 @zRains
// function pr(a, s = a.length, r = []) {...}
// function co(a, k) {...}

/**
 *
 * @param {number[]} a
 * @param {number} m
 * @return {any[][]}
 */
function gr(a, m) {
  const res = []

  co(a, m).forEach((c) => res.push(...pr(c)))

  return res
}

/**
 *
 * @param {Map<any, number>} map
 * @param {number} max
 */
const rs = (map, max) => {
  const res = []
  map.forEach((v, k) => void res.push(...Array(Math.min(max, v)).fill(k)))
  return res
}

/**
 *
 * @param {number} x
 * @param {string} o
 * @param {number} y
 * @returns
 */
function cs(x, o, y) {
  if (o === '+') return x + y
  if (o === '-') return x - y
  if (o === '*') return x * y
  if (o === '**') return x ** y
  if (o === '//') return Math.floor(x / y)
  if (o === '%') return x % y
  if (o === '|') return x | y
  if (o === '&') return x & y
  if (o === '^') return x ^ y
  if (o === '>>') return x >> y
  if (o === '<<') return x << y

  throw new Error(`未知符号：${o}`)
}

/**
 *
 * @param {number[]} n
 * @param {string[]} s
 */
function ca(n, s) {
  let n1 = n[0]
  for (let i = 0; i < 3; i++) n1 = cs(n1, s[i], n[i + 1])
  return n1
}

/**
 *
 * @param {any[]} arr
 * @param {boolean} [isNum]
 */
function unique(arr, isNum = true) {
  const set = new Set()
  arr.forEach((a) => set.add(a.join('#')))
  return [...set.values()].map((a) => a.split('#').map((v) => (isNum ? parseInt(v) : v)))
}

/**
 *
 * @param {number[]} _n
 * @param {string[]} _s
 */
function $1024$(_n, _s) {
  const result = []
  const [cardMap, symbolMap] = [_n, _s].map((a) => {
    let map = new Map()
    a.forEach((c) => {
      let v = !isNaN(c) ? Number.parseInt(c) : c
      map.set(v, 1 + (map.get(v) || 0))
    })
    return map
  })

  const numbers = rs(cardMap, 4),
    symbols = rs(symbolMap, 3)

  if (numbers.length < 4 || symbols < 3) throw new Error('没有足够的数字卡或符号卡')

  const numGroups = unique(gr(numbers, 4)),
    symGroups = unique(gr(symbols, 3), false)

  for (n of numGroups) {
    for (s of symGroups) {
      if (ca(n, s) === 1024) {
        result.push(`(((${n[0]} ${s[0]} ${n[1]}) ${s[1]} ${n[2]}) ${s[2]} ${n[3]})`)
      }
    }
  }
}

// Solution_2 @LetMeFly666
function mainOriginal(numbers, operators) {
  const ans = []
  for (var n1 = 0; n1 < numbers.length; n1++) {
    for (var n2 = 0; n2 < numbers.length; n2++) {
      for (var n3 = 0; n3 < numbers.length; n3++) {
        for (var n4 = 0; n4 < numbers.length; n4++) {
          if (n1 == n2 || n1 == n3 || n1 == n4 || n2 == n3 || n2 == n4 || n3 == n4) continue
          for (var o1 = 0; o1 < operators.length; o1++) {
            for (var o2 = 0; o2 < operators.length; o2++) {
              for (var o3 = 0; o3 < operators.length; o3++) {
                if (o1 == o2 || o1 == o3 || o2 == o3) continue
                const string = `(((${numbers[n1]} ${operators[o1]} ${numbers[n2]}) ${operators[o2]} ${numbers[n3]}) ${operators[o3]} ${numbers[n4]})`
                try {
                  if (eval(string) == 1024) ans.push(string)
                } catch (e) {
                  // 分母为0一般是
                }
              }
            }
          }
        }
      }
    }
  }
  return ans
}

// benchmark
suite
  .add('Solution_1 @zRains', function () {
    solution_1([1024, 1024, 1024, 11, 11, 34], ['>>', '>>', '>>', '>>', '<<', '|'])
  })
  .add('Solution_2 @LetMeFly666', function () {
    solution_2([1024, 1024, 1024, 11, 11, 34], ['>>', '>>', '>>', '>>', '<<', '|'])
  })
  .on('cycle', function (event) {
    console.log(String(event.target))
  })
  .on('complete', function () {
    console.log('Fastest is ' + this.filter('fastest').map('name'))
  })
  .run({ async: true })

结果：

Solution_1 @zRains x 10,095 ops/sec ±0.26% (94 runs sampled)
Solution_2 @LetMeFly666 x 80.51 ops/sec ±0.26% (71 runs sampled)
Fastest is Solution_1 @zRains

另外我发现用js实现存在一部分值被忽略了，比如下面的值：

(((11 >> 34) >> 1024) | 1024)

我推测是因为js的位运算支持32位数字，右移过多会出现诡异的bug。目前还没有解决的方法。

[LetMeFly666]

您的issue已收到！非常感谢您的建议，抱歉这么久才回复。

我将尽快进行研究，👍

[LetMeFly666]

再次感谢大佬提供的算法，已采用👍

[zRains]

感谢认可，但最为推荐的做法是通过python这种无视精度限制的脚本，js只能判定是否可能存在结果。我在leetcode测试过了，虽然计算的结果是1024，但leetcode不是通过js计算的。我正在尝试用wasm解决

[LetMeFly666]

不知大佬是否有意向成为Collaborator
在此表示非常欢迎