3

I'm trying to use matrix algebra with the purpose of manipulating strings. This means being able to multiple matrix-like structures using concatenation and pasting of string or of arrays of strings.

I previously tried to implement the thing on R, but it was not possible as matrices can have only one dimensional entries.

I hope to be enough language-agnostic and abstract, but I'll use R-like code for sake of clarity. I should make explicit that I don't require real matrices, but matrix-like structure on which we can do matrices-like multiplication and retrieve the (ij) element of the structure.

{+,*} MATRICES MULTIPLICATION

两个n 维方阵A和B的 {+,*}-乘积是由以下元素定义的矩阵C： C i,j = Sum k=1,...,n A i,k * B k, Ĵ。

例如，考虑矩阵 M <- matrix(c(a,b,0,0,c,d,0,0,e),3,3)。那么 M 乘以 M 就是 M <- matrix(c(a^2,a*b+b*c,b*d,0,c^2,c*d+d*e,0,0,e^2),3,3)。

{c(,),paste0(,)} 矩阵乘法

我想实现的这个操作的规则与前面所说的乘法相同，其中的基本突变是总和应该是一个连接，而乘积应该是一个粘贴。换句话说，我们在前面的公式中找到a+b，现在输出应该是“c(a,b)”，当我们找到 时a*b，现在我们应该将其读为paste0(a,b)。

必须尊重一些通常的属性，即分配属性和 0 元素属性。因此，如果a <- c("q",0,"w")和b <- c("e")然后a*b <- c("qe",0,"we")（我们应该随意忘记 0 元素，将其删除，因为它不会影响计算。

此外，我们正在乘以等维矩阵，因此每个元素 C i,j = Sum k=1,...,n A i,k * B k,j现在被读作 c("A[i,1]B[1,j]",...,"A[i,n]B[n,j]")。

最后，类似结果矩阵的结构应该是我们可以再次用于计算的东西（例如，进行更复杂的计算，如 mult(mult(A,B),C) 等等......）。

一个更简单的案例

为简单起见，让我们从计算形式的乘积开始mult(A,A)，mult(mult(A,A),A)以此类推。我们也可以将A强加为一个简单的矩阵，这意味着它的每个元素都是一维字符串，而不是字符串的串联。

让我们举个例子。让我们将A定义为 3 维矩阵 A <- matrix(c("a","b",0,0,"c","d",0,0,"e"),3,3)，那么A乘以A应该是 mult(A,A) = matrix(c("aa",c("ab","bc"),"bd",0,"cc",c("cd","de"),0,0,"ee"),3,3) 并且A 3应该是 mult(mult(A,A),A) = matrix(c("aaa",c("aab","abc","bcc"),c("abd","bcd","bde"),0,"ccc",c("ccd","cde","dee"),0,0,"eee"),3,3)。

问题

你将如何实现这一点？哪种语言看起来更合适？

4

1 回答 1

2

以下是 R 中矩阵符号乘法的一些想法：

首先我们需要定义行和列的内积。这可以通过以下方式完成：

wrap <- function(x) paste0("(",x,")")

rowcol <- function(row,col) paste(wrap(row),wrap(col),sep="*",collapse="+")

例子：

> rowcol(c("A","B","C"),c("D","E","F"))
[1] "(A)*(D)+(B)*(E)+(C)*(F)"

我不得不将每个元素“包装”在括号中，因为大于 2 的幂可能比单个变量或数字（零）具有更复杂的表达式。另外，请注意，零将正常显示，即，它不知道（尚）这些可以简化：

> rowcol(c("A","B"),c("0","X+Y"))
[1] "(A)*(0)+(B)*(X+Y)"

由于这些是 R 中的有效表达式，因此可以使用此事实编写简化函数以消除零和多余的括号。我会到达那里。

现在矩阵乘法和幂很简单：

symprod <- function(A,B) sapply(1:ncol(B), function(j)sapply(1:nrow(A), function(i)rowcol(A[i,],B[,j])))

sympow <- function(A,n) { B <- A; for( i in seq_len(n-1) ) B <- symprod(B,A); B }

他们创建了有效的（虽然笨拙的）表达式：

> A <- matrix(LETTERS[1:4],2,2)
> diag(A) <- 0
> sympow(A,3)
     [,1]                                          [,2]                                         
[1,] "((0)*(0)+(C)*(B))*(0)+((0)*(C)+(C)*(0))*(B)" "((0)*(0)+(C)*(B))*(C)+((0)*(C)+(C)*(0))*(0)"
[2,] "((B)*(0)+(0)*(B))*(0)+((B)*(C)+(0)*(0))*(B)" "((B)*(0)+(0)*(B))*(C)+((B)*(C)+(0)*(0))*(0)"

现在让我们谈谈简化。这些字符串可以解析为有效的 R 表达式，因为它们符合 R 标准。不需要定义变量，因为我们不会评估表达式。实际上我只想解析它们以简化。

检查下面的功能。它删除了多余的括号，用零替换了零乘以任何东西，并删除了零的包裹（添加）：

simplify <- function(e)
{
    if( mode(e) %in% c("name","numeric") ) return(e)

    if( as.character(e[[1]])=="+" )
    {
        x <- simplify(e[[2]])

        y <- simplify(e[[3]])

        if( identical(x,0) ) return(y)

        if( identical(y,0) ) return(x)

        return(call("+", x, y))
    }

    if( as.character(e[[1]])=="*" )
    {
        x <- simplify(e[[2]])

        if( identical(x,0) ) return(0)

        y <- simplify(e[[3]])

        if( identical(y,0) ) return(0)

        return(call("*", x, y))
    }

    if( as.character(e[[1]])=="(" )
    {
        x <- simplify(e[[2]])

        if( mode(x) %in% c("name","numeric") ) return(x)

        return(call("(", x))
    }
}

此函数适用于call对象。要与我们需要的字符串一起使用

simplify_text <- function(s) deparse(simplify(parse(text=s)[[1]]))

例子：

> simplify_text("(x)+(0*(a+b))+(z)")
[1] "x + z"

如果需要，可以将其用作包装器rowcol：

rowcol <- function(row,col) simplify_text(paste(wrap(row),wrap(col),sep="*",collapse="+"))

结果是：

> sympow(A,3)
     [,1]          [,2]         
[1,] "0"           "(C * B) * C"
[2,] "(B * C) * B" "0"

可以编写其他一些简化，这取决于计划如何使用它们。但是，如果输入矩阵是有效表达式的字符串，则最终结果仍然有效。

编辑：另一种方法rowcol：

考虑这些函数：

cellprod <- function(r, s)
{
    z <- expand.grid(r,s, stringsAsFactors=FALSE)

    filter <- (z$Var1 != 0) & (z$Var2 != 0)

    paste(z$Var1[filter], z$Var2[filter], sep="*", collapse="+")
}

rowcol <- function(row,col)
{
    x <- strsplit(row, "\\+")

    y <- strsplit(col, "\\+")

    L <- vapply(seq_along(x), function(i) cellprod(x[[i]],y[[i]]), character(1))

    filter <- nzchar(L)

    if( ! any(filter) ) return("0")

    paste(L[filter], collapse="+")
}

Using these instead of the functions above, we can handle matrices with expressions of the form x*y*z+a*b+f, i. e., sums of products in each cell. The functions automatically applies the distributive law, preserving the form (sum-of-products) and also removes zeros automatically. The last example above becomes:

> sympow(A,3)
     [,1]    [,2]   
[1,] "0"     "C*B*C"
[2,] "B*C*B" "0"

No simplification required! Another example:

> A <- matrix(LETTERS[1:9],3,3)
> B <- matrix(LETTERS[10:18],3,3)
> A[2,3] <- 0
> A[3,2] <- 0
> B[1,3] <- 0
> B[3,1] <- 0
> A
     [,1] [,2] [,3]
[1,] "A"  "D"  "G" 
[2,] "B"  "E"  "0" 
[3,] "C"  "0"  "I" 
> B
     [,1] [,2] [,3]
[1,] "J"  "M"  "0" 
[2,] "K"  "N"  "Q" 
[3,] "0"  "O"  "R"
> symprod(A,B)
     [,1]      [,2]          [,3]     
[1,] "A*J+D*K" "A*M+D*N+G*O" "D*Q+G*R"
[2,] "B*J+E*K" "B*M+E*N"     "E*Q"    
[3,] "C*J"     "C*M+I*O"     "I*R"
于 2013-04-01T17:03:44.477 回答