Rust 编写的化学方程式配平库 - V2EX
https://www.v2ex.com/t/456064#reply12

#Math https://baike.baidu.com/item/%E9%BD%90%E6%AC%A1%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84

(齐次线性方程组)
齐次线性方程组：常数项全部为零的线性方程组。如果m<n(行数小于列数，即未知数的数量大于所给方程组数），则齐次线性方程组有非零解，否则为全零解。

#Math （线性代数 领域）齐次线性方程组（homogeneous linear equations ）

常数项全为0的n元线性方程组（也即齐次线性方程组） 是什么样的呢？

equation = {
a11 x1 + a12 x2 + ... + a(10)n xn = 0,
a21 x1 + a22 x2 + ... + a(20)n xn = 0,
...
am1 x1 + ... + amn xn = 0
}

涉及的矩阵 a 包含矩阵类型的元素，索引 [m, n]
m 为等式矩阵的行号，n 则为列号

基本性质 如果m<n(行数小于列数，即未知数的数量大于所给方程组数），则齐次线性方程组有非零解，否则为全零解

a[1, 1] a[1, 2] a[2, 1]...

这种等式连立模式称为n元齐次线性方程组。设其系数矩阵为 A，未知项为 X，则其矩阵形式为 AX=0。若设其系数矩阵经过初等行变换所化到的行阶梯形矩阵的非零行行数为r，则它的方程组的解只有以下两种类型：

当 r=n 时，原方程组仅有零解；
当 r<n 时，有无穷多个解（从而有非零解）。

那么，怎么解它而求得方程的解集？

1. 依照 m<n 属性判断是否有解
2. 对等式项的系数实施初等行变换，得到齐次线性方程组
3. 解方程组

instance:

type x: matrix2
hle1 = {
  x1 - 3x2 + x4 = 0,
  x1 + 2x2 - x3 - x4 = 0,
  x2 + 2x3 - 2x4 = 0
}

此时，等式的连立数 m 为 3，未知数矩阵长 n 为 4，有解
可以模式匹配得到系数矩阵 v 为

hle1' = {
  x1 + (-1)(3)x2 + (0)x3 + x4 = 0,
  x1 + (2)x2 + (-1)x3 + (-1)x4 = 0,
  (0)x1 + x2 + (2)x3 + (-1)(2)x4 = 0,
}

type v: martix2
v = [
  [1, -3, 0, 1],
  [1, 2, -1, -1],
  [0, 1, 2, -2]
]

len(v) 就是上文的 r
r=0 时，方程仅有零解
r<n 时，方程有无穷多个解
在这里，n = len(v.sigle())

此谓系数矩阵『A』，AX=0，X 是一个矩阵索引 m*(n-1)+i
== 逆向操作：利用系数矩阵也可以得到原零等式连立

foreach ((vi, m) in v.pairs) {
  type result: equationGroup
  result << (= 0) . foldLeftIndex (m, new equation(0)) do |k, i| { (k xi +) }
}

也可以得到原等式组

result = {
  1 x1 + 2 x2 + (-1 x3) + 1 x4 = 0,
  1 x1 + (-3 x2) + 0 x3 + 1 x4 = 0,
  0 x1 + 1 x2 + 2 x3 + (-2 x4) = 0
} = hle1 

对矩阵 v 施用初等行变换并且化简，得到矩阵 v'

type v': matrix2
v' = [
  [1, 0, 0, -7/11],
  [0, 1, 0, -6/11],
  [0, 0, 1, -8/11]
]

套用得等式组

fin = {
  x1 + (0)x2 + (0)x3 - (-7/11)x4 = 0,
  (0)x1 + x2 + (0)x3 - (-6/11)x4 = 0,
  (0)x1 + (0)x2 + x3 - (-8/11)x4 = 0,
}

即得。
然后这就非常线性了，x4 可以是任意实数 _<{R}
相对 x4 的解集为元组 ((-7/11), (-6/11), (-8/11), 1)

这里不关心性质的证明什么的，扔给数学家们去做吧。计算机科学算法还是很实用的（

🤔 我们在计算机们里面怎么抽象这种算法呢？

🤔 那么，既然我们知道了这种数学算法，而且又知道它可以被计算机求解，怎么写出对应的算法呢？

首先看看我们的问题：我们要解类似下面这种 齐次线性方程组

hle1 = {
x1 - 3x2 + x4 = 0,
x1 + 2x2 - x3 - x4 = 0,
x2 + 2x3 - 2x4 = 0
}

它可以被抽象为以下形式，便于变换：

typealias Real = Double
class HomogeneousLinearEquation {
  // v[m, 1] * x[1] + .. + v[m, n] * x[n] = 0
  val co: Vector</* m */Vector</* n */Real>>
  val vx: Vector</* n */Real>
}

我们可以写一个函数来 dump 这种数据结构

fun HmomgeneousLinearEquation.toString(): String {
val sb = StringBuilder()

val r = co.size
val n = vx.size

for (m in 0..r-1) {
for (i in 0..n-1) {
sb.write(String.format("co[%d, %d] * x[%d] + ", m, n, n))
}
}

return sb.write("0 = 0").toString()
}

好吧，很不函数式，不过依然可以用，我们看看：

既然是这么学术（迫真）的东西就用 Haskell 好了（大嘘） 🙈
虽然数学不好驾驭不了 Haskell

module HomogenLineq where

那么我们也可以修改一下自己的建模，就语法解析前端来看，我们认为只存在 + 和 * 两种组合方式，组合的目标是 Int 或者组合结果本身，而 - 和 / 分别使用负数和分数来解决

就后端来看，一个 HLEs 实际上是由一组常数为零的多项式构成的，也就是说

data HomogenLineqGroup = List HomogenLineq

而一个 HLE 则是由一打系数和未知数索引（这里我的描述方法）构成的，他们之间使用 + 组合

data HomogenLineq = List Monomial
data Monomial = MulCoeffX Num Num


那么使用这种很不方便的数据结构（因为后面的变形可能会证明这么抽象是很麻烦很不 effective 的，不过这里只是演示就不考虑性能问题，随便瞎 🐔 玩）

可以这么表示我们要处理的对象

hle1 = [MulCoeffX 1 1, MulCoeffX (-3) 2, MulCoeffX 0 3, MulCoeffX 1 4] : [MulCoeffX 1 1, MulCoeffX 2 2, MulCoeffX (-1) 3, MulCoeffX (-1) 4] : [MulCoeffX 0 1, MulCoeffX 1 2, MulCoeffX 2 3, MulCoeffX (-2) 4] : []


所以有

{-- v[m, 1] * x[1] + ... + v[m, n] * x[n] = 0 --}

module HomogenLineq where
    {-- v[m, n] * x[n] --}
    data MonomialMultiplication a = MulCoeffX a a

    type Monomial = MonomialMultiplication Int

    {-- v[m, n] * x[n] + ... --}
    type HomogenLineq = [Monomial]
    type HomogenLineqGroup = [HomogenLineq]

    hle1 :: HomogenLineqGroup
    hle1 = [MulCoeffX 1 1, MulCoeffX (-3) 2, MulCoeffX 0 3, MulCoeffX 1 4] : [MulCoeffX 1 1, MulCoeffX 2 2, MulCoeffX (-1) 3, MulCoeffX (-1) 4] : [MulCoeffX 0 1, MulCoeffX 1 2, MulCoeffX 2 3, MulCoeffX (-2) 4] : []

    dumpItem :: Show t => MonomialMultiplication t -> String
    dumpItem (MulCoeffX coe x) = "(" ++ show coe ++ "*x" ++ show x ++ ")"

    dumpEquation :: HomogenLineq -> String
    dumpEquation = foldr (\s tl -> dumpItem s ++ " + " ++ tl) "0 = 0"

    dumpEquations :: HomogenLineqGroup -> String
    dumpEquations = foldr (\l tl -> "  " ++ dumpEquation l ++ "," ++ nl tl ++ tl) ""
        where nl tl = if length tl == 0 then "" else "\n"

    dump' :: String -> HomogenLineqGroup -> String
    dump' name g = name ++ " = {\n" ++ dumpEquations g ++ "\n}"

    dump :: HomogenLineqGroup -> String
    dump = dump' "(anon)"

🤔 值不值得...

所以现在我连变形『前端』（解析器）的工作都还没有完成，然后只写了点模式化的代码... 累了 🌝

v = [
  [1, -3, 0, 1],
  [1, 2, -1, -1],
  [0, 1, 2, -2]
]

到

v' = [
  [1, 0, 0, -7/11],
  [0, 1, 0, -6/11],
  [0, 0, 1, -8/11]
]

该怎么办？

不知道，或许可以看这里
但我真的不熟悉 Haskell 啊... 别说范畴论和 Monad 了，就是普通一点的算法列表 / Records / Tuple 处理向的都不会...
又要用 Data.Map... Haskell 是非常理论的， Data.Map 就是 LinkedMap 而已嘛。空间还蛮省的，就是 O(n) 时间复杂度大了点

变形到

fin = {
  x1 + (0)x2 + (0)x3 - (-7/11)x4 = 0,
  (0)x1 + x2 + (0)x3 - (-6/11)x4 = 0,
  (0)x1 + (0)x2 + x3 - (-8/11)x4 = 0,
}

只需要一点基础的数学功底，但我有点不清楚表达式该怎么写，把所有 x1-x3 相乘再 / x4？
还是好好学 Rust？（‘

#Share #Haskell #code 这货唯一的作用，可能就是给那些 Haskell 都不会的 🐔 们入门... 连入门都做不到，因为没教范畴论也没教各种 typeclass Constraint instance records recursion...

附注，他为自己的算法专门排了篇论文，在这里可以阅读
博文在这里 https://lexuge.github.io/jekyll/update/2018/02/20/XCH%E7%99%BD%E7%9A%AE%E4%B9%A6.html

#Rust #blog #net #Performance https://lexuge.github.io/jekyll/update/2018/07/24/lib_blaster%E4%BC%98%E5%8C%96%E7%AC%94%E8%AE%B0.html

https://www.cnblogs.com/conmajia/p/no-overdesign-just-experiment.html

再看看您这个优化的 🐔 呢？连 dns 解析到底花了多少时间都不知道！

这个使用的算法就是暴力搜索（从 0 枚举到 n，不停枚举化学配平系数、然后算粒子个数对比，成功就好，不成功继续下一轮），总的来看其实它作为解析器的部分是最有价值的...

虽然的确和作者说的一样，是比较烂的代码（虽然是 C 写的，比较底层）
但是看了一会也勉强能找到逻辑，解析器什么的我其实也会写，我写的第一个能嵌套的解析器使用的 subsequence 方法和这个里面实现的一致

暴力查找算法的入口在 366 行，int check();



int check_int_exp(int alpha,int beta,int mode)
{
  bool ans=false;
  int c=0;
  if (mode==1) ans=__builtin_sadd_overflow(alpha,beta,&c);
  if (mode==2) ans=__builtin_smul_overflow(alpha,beta,&c);
  if (ans==true) wrong_exit(6);
  return 0;
}

[lexuge@localhost XCH]$ ./XCH

XCH - Chemical Equation Balancer
By LEXUGE
Copyright (2017-2017) LEXUGE
The software is using GPL(http://www.gnu.org/licenses/gpl.txt)
------Input------
输入有几种元素种类,几个分子式，等号左边，右边的分子式个数：
5 6 3 3
输入每种元素包含的原子在方程式中各个分子式的个数：
2 0 0 1 0 0
3 0 0 0 0 1
0 1 0 0 1 0
0 0 1 3 0 2
0 0 1 0 2 0
输入搜索最大值:
50
------Output------
各分子式系数分别为：
1 6 12 2 6 3

https://lexuge.github.io/jekyll/update/2017/03/12/XCH-%E5%8C%96%E5%AD%A6%E6%96%B9%E7%A8%8B%E5%BC%8F%E9%85%8D%E5%B9%B3%E7%A8%8B%E5%BA%8F.html


当然，你们上面拿到的那个是后来的改进版，它不需要你手动算上面要求输入的数据自己输了，你可以直接输入配平等式，解析器前端 xch_parser() 可以解决数据的问题，不过我不知道『

每种元素包含的原子在方程式中各个分子式的个数

』是哪里来的，可能是把数据写外面了吧...

#dev 是啊，现在 DVCS 时代，比以前还没有 VCS 系统靠死版本迭代的时候，强多了。

啊 不知道赞叹过多少次了 还是要赞叹一下 git
自己家两台电脑 + 学校电脑 要开始写代码了直接 git pull 然后干活就行（— Rachel (ﾉД`)ｼｸｼｸ (@tangrui003) March 9, 2019

Telegram X 今日 beta 更新支持投票功能，在 Google play 里加入 tgx 的 beta 测试就可以更新啦

(直译为：
啊 不知道赞叹过多少次了 还是要赞叹一下混蛋

官方逼死同人你说呢 @vote?

https://t.me/dsuse/9440

可是 没记错的话 这个 @vote 不应该是官方的么（