python - 模2 python代码中的高斯消除

Question

我想知道模 2 中的高斯消元法(或什至通常为此目的模 k 中的高斯消元法)是否曾经在某个地方实现过，这样我就不必重新发明轮子而只需使用可用资源？

Answer 1

您要查找的算法的伪代码存在并且是:

    // A is n by m binary matrix
    i := 1 // row and column index
    for i := 1 to m do // for every column
      // find non-zero element in column i, starting in row i:
      maxi := i
      for k := i to n do
        if A[k,i] = 1 then maxi := k
      end for
      if A[maxi,i] = 1 then
        swap rows i and maxi in A and b, but do not change the value of i
        Now A[i,i] will contain the old value of A[maxi,i], that is 1
        for u := i+1 to m do
          Add A[u,i] * row i to row u, do this for BOTH, matrix A and RHS vector b
          Now A[u,i] will be 0
        end for
     else
       declare error – more than one solution exist
     end if
   end for
   if n>m and if you can find zero row in A with nonzero RHS element, then
     declare error – no solution.
   end if
   // now, matrix A is in upper triangular form and solution can be found
   use back substitution to find vector x

取自此pdf

二进制算术意味着以 2 为模的算术，如果我没记错的话，这就是您在问题中寻找的内容。

很遗憾，我不会用 Python 编写代码，但是如果您熟悉 Python，您可以简单地将上面的伪代码按您自己的方式逐行翻译成 Python，以方便您完成此任务两者都不是 困难也不 长。

我搜索了“gaussian elimination modulo 2 python”，但没有找到你要找的python代码，但我认为这是好的，因为在翻译过程中你可能会更好地理解算法和方法。

编辑 1:如果您也熟悉 C# 并且将 C# 转换为 Python 并不费力，那么 Michael Anderson 对此 question 的回答也可能对您有所帮助。

编辑 2:发布答案后，我继续搜索并找到了 this

“over any field”意味着“over modulo 2”，甚至对于任何 k≥2 的“over modulo k”。

它包含 Java 版本和 Python 版本的源代码。

根据我为您提供的 Python 版本的最后一个链接，fieldmath.py 包含类 BinaryField，它假设是 modulo 2如你所愿。

尽情享受吧!

我只是希望Gauss-Jordan elimination和Gaussian Elimination不是两个不同的东西。

编辑 3:如果您还熟悉 VC++ 并且将 VC++ 转换为 Python 对您来说不是那么您也可以尝试 this .

我希望这能很好地回答您的问题。