我如何确保候选拉丁方是有效的 Damm 操作 Table

Question

我正在尝试在 Scala 中编写一个函数，该函数采用有效的 Latin Square as input and then returns a Boolean value indicating whether the input Latin Square is a valid instance of an operation-table for the Damm Algorithm, or not. The Damm Algorithm appears to be of the "Check digit" class 错误检测机制。

所需函数是 Design section of the Wikipedia article for the Damm Algorithm 中描述的含义的实现。其含义由以下断言捕获：

a weak totally anti-symmetric quasigroup with the property x ∗ x = 0

我的数学技能不足以正确阅读和解释 Damm 的论文，也没有足够的德语（论文写作语言）阅读能力来自信地解释我将如何编码正确的验证函数。

给定以下函数定义：

def validate(latinSquare: List[List[Int]]): Boolean =
  ???

我会用什么来代替 ???？

在本文中，提供了一个有效的 10x10 拉丁方块实例。它是 reproduced within the Wikipedia article，看起来像这样：

 |0 1 2 3 4 5 6 7 8 9
-+-------------------
0|0 3 1 7 5 9 8 6 4 2
1|7 0 9 2 1 5 4 8 6 3
2|4 2 0 6 8 7 1 3 5 9
3|1 7 5 0 9 8 3 4 2 6
4|6 1 2 3 0 4 5 9 7 8
5|3 6 7 4 2 0 9 5 8 1
6|5 8 6 9 7 2 0 1 3 4
7|8 9 4 5 3 6 2 0 1 7
8|9 4 3 8 6 1 7 2 0 5
9|2 5 8 1 4 3 6 7 9 0

我可以看到there are others who have 。但是，还没有人提供所请求的基于代码 有效的拉丁方解决方案。

我已经编写了一个通用的拉丁方生成器，但需要上述验证函数作为过滤器，以消除不满足上述蕴涵必要条件的每个候选拉丁方。

Answer 1

在函数式编程术语中，校验和算法是 foldLeft 并精心选择了二进制运算。这个二元运算的要求，英文：

在每个 two-digit 输入中，如果我们更改其中一个数字，则校验和也会更改（拉丁方...）；
在每个 three-digit 输入中，如果后两位数字不同并且我们交换它们，则校验和会发生变化（...总反对称性较弱）；
拉丁方在对角线上有零。

在Python 3:

def validate(latinSquare):
    Q = range(len(latinSquare))
    return all(
        x == y
        for c in Q
        for x in Q
        for y in Q
        if latinSquare[latinSquare[c][x]][y] == latinSquare[latinSquare[c][y]][x]
    ) and all(latinSquare[x][x] == 0 for x in Q)


print(
    validate(
        [
            [0, 3, 1, 7, 5, 9, 8, 6, 4, 2],
            [7, 0, 9, 2, 1, 5, 4, 8, 6, 3],
            [4, 2, 0, 6, 8, 7, 1, 3, 5, 9],
            [1, 7, 5, 0, 9, 8, 3, 4, 2, 6],
            [6, 1, 2, 3, 0, 4, 5, 9, 7, 8],
            [3, 6, 7, 4, 2, 0, 9, 5, 8, 1],
            [5, 8, 6, 9, 7, 2, 0, 1, 3, 4],
            [8, 9, 4, 5, 3, 6, 2, 0, 1, 7],
            [9, 4, 3, 8, 6, 1, 7, 2, 0, 5],
            [2, 5, 8, 1, 4, 3, 6, 7, 9, 0],
        ]
    )
)

Answer 2

这是由 David Eisenstat 的回答提供的到 Scala 的转换。

View in Scastie:

def isValidDammOperationTable(validLatinSquare: List[List[Int]]): Boolean = {
  val indices = validLatinSquare.indices.toList
  (
        indices.forall(index => validLatinSquare(index)(index) == 0)
    &&  indices.forall(
          c =>
            indices.forall(
              x =>
                indices.forall(
                  y =>
                        (validLatinSquare(validLatinSquare(c)(x))(y) != validLatinSquare(validLatinSquare(c)(y))(x))
                    ||  (x == y)
                )
            )
        )
  )
}

val exampleLatinSquareX10: List[List[Int]] =
  List(
      List(0, 3, 1, 7, 5, 9, 8, 6, 4, 2)
    , List(7, 0, 9, 2, 1, 5, 4, 8, 6, 3)
    , List(4, 2, 0, 6, 8, 7, 1, 3, 5, 9)
    , List(1, 7, 5, 0, 9, 8, 3, 4, 2, 6)
    , List(6, 1, 2, 3, 0, 4, 5, 9, 7, 8)
    , List(3, 6, 7, 4, 2, 0, 9, 5, 8, 1)
    , List(5, 8, 6, 9, 7, 2, 0, 1, 3, 4)
    , List(8, 9, 4, 5, 3, 6, 2, 0, 1, 7)
    , List(9, 4, 3, 8, 6, 1, 7, 2, 0, 5)
    , List(2, 5, 8, 1, 4, 3, 6, 7, 9, 0)
  )

println(isValidDammOperationTable(exampleLatinSquareX10)) //prints "true"

我如何确保候选拉丁方是有效的 Damm 操作 Table

How Do I Ensure a Candidate Latin Square Is a Valid Damm Operation Table

algorithm

scala

check-digit