{"version":3,"file":"gauss.js","sourceRoot":"","sources":["../../../../src/chart/layout/constraint/gauss.ts"],"names":[],"mappings":"AAAA;;;;GAIG;AACH,MAAM,UAAU,KAAK,CAAC,CAAa;IACjC,IAAM,GAAG,GAAG,CAAC,CAAC,MAAM,CAAC;IACrB,IAAM,GAAG,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,MAAM,CAAC;IAExB,IAAM,CAAC,GAAG,GAAG,CAAC,CAAC,QAAQ;IACvB,IAAM,CAAC,GAAG,GAAG,GAAG,CAAC,CAAC,CAAC,iBAAiB;IAEpC;;;OAGG;IACH,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;QAC1B,qBAAqB;QACrB,IAAI,GAAG,GAAG,MAAM,CAAC,gBAAgB,CAAC;QAClC,IAAI,MAAM,SAAA,CAAC;QACX,kBAAkB;QAClB,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;YAC1B,IAAI,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,GAAG,EAAE;gBAC3B,GAAG,GAAG,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;gBACxB,MAAM,GAAG,CAAC,CAAC;aACZ;SACF;QAED,qBAAqB;QACrB,IAAM,GAAG,GAAG,CAAC,CAAC,MAAM,CAAC,CAAC;QACtB,CAAC,CAAC,MAAM,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC;QACjB,CAAC,CAAC,CAAC,CAAC,GAAG,GAAG,CAAC;QAEX,yBAAyB;QACzB,KAAK,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;YAC9B,OAAO;YACP,IAAM,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;YAC7B,aAAa;YACb,KAAK,IAAI,CAAC,GAAG,CAAC,EAAE,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,EAAE,EAAE;gBAC9B,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;aACxB;SACF;KACF;IAED;;OAEG;IACH,IAAM,CAAC,GAAG,IAAI,KAAK,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC;IAE/B,uBAAuB;IACvB,KAAK,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,IAAI,CAAC,EAAE,CAAC,EAAE,EAAE;QAC/B,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;QAEzB,SAAS;QACT,KAAK,IAAI,CAAC,GAAG,CAAC,GAAG,CAAC,EAAE,CAAC,IAAI,CAAC,EAAE,CAAC,EAAE,EAAE;YAC/B,IAAM,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC;YAC7B,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC;YACvB,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,IAAI,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,CAAC,GAAG,CAAC,CAAC;SACxB;KACF;IAED,OAAO,CAAC,CAAC;AACX,CAAC;AAED;;;GAGG;AACH,MAAM,UAAU,QAAQ,CAAC,CAAW;IAClC,OAAO,CAAC,CAAC,MAAM,CAAC,UAAC,CAAC,EAAE,CAAC,IAAK,OAAA,CAAC,GAAG,CAAC,EAAL,CAAK,EAAE,CAAC,CAAC,CAAC;AACtC,CAAC","sourcesContent":["/**\n * Gaussian elimination\n * @param  array a matrix\n * @return array x solution vector\n */\nexport function gauss(a: number[][]): number[] {\n  const row = a.length;\n  const col = a[0].length;\n\n  const m = row; // 方程的个数\n  const n = col - 1; // 变量的个数(最后一列是常量)\n\n  /**\n   * 先对 a 进行排序，排序规则为：\n   * - 第 i 列对应从 i 行到最后一行的最大值，放到当前行\n   */\n  for (let i = 0; i < n; i++) {\n    // 1. 找到这一列的最大值、已经行索引\n    let max = Number.MIN_SAFE_INTEGER;\n    let maxRow;\n    // 找到这一列的最大值、已经行索引\n    for (let j = i; j < m; j++) {\n      if (Math.abs(a[j][i]) > max) {\n        max = Math.abs(a[j][i]);\n        maxRow = j;\n      }\n    }\n\n    // 2. 找到这一列的最大值之后，交换行\n    const tmp = a[maxRow];\n    a[maxRow] = a[i];\n    a[i] = tmp;\n\n    // 3. 这一行下面，在这一列上的数据全部为 0\n    for (let j = i + 1; j < m; j++) {\n      // 配平系数\n      const c = -a[j][i] / a[i][i];\n      // 这一行的元素全部处理\n      for (let k = i; k < n + 1; k++) {\n        a[j][k] += c * a[i][k];\n      }\n    }\n  }\n\n  /**\n   * 反向迭代，计算变量值\n   */\n  const b = new Array(n).fill(0);\n\n  // 只有 n 个变量（n 后的方程直接忽略）\n  for (let i = n - 1; i >= 0; i--) {\n    b[i] = a[i][n] / a[i][i];\n\n    // 向上带入归零\n    for (let j = i - 1; j >= 0; j--) {\n      const c = -a[j][i] / a[i][i];\n      a[j][i] += a[i][i] * c;\n      a[j][n] += a[i][n] * c;\n    }\n  }\n\n  return b;\n}\n\n/**\n * 乘法\n * @param v\n */\nexport function multiply(v: number[]) {\n  return v.reduce((r, c) => r * c, 1);\n}\n"]}