14

R-help上有一个有趣的问题：

“把数字从一到十七。你能把它们写成一行，这样每对相邻的数字加起来就是一个平方数吗？”

我的解决方案如下，并不是特别特别。我对更优雅和/或更强大的解决方案感到好奇。如果可能的话，也许一个可以采用任意数字字符串并像这样对它们进行排序的解决方案？

sq.test <- function(a, b) {
  ## test for number pairs that sum to squares.
  sqrt(sum(a, b)) == floor(sqrt(sum(a, b)))
}

ok.pairs <- function(n, vec) {
  ## given n as a member of vec,
  ## which other members of vec satisfiy sq.test
  vec <- vec[vec!=n]
  vec[sapply(vec, sq.test, b=n)]
}

grow.seq <- function(y) {
  ## given a starting point (y) and a pairs list (pl)
  ## grow the squaring sequence.
  ly <- length(y)
  if(ly == y[1]) return(y)

  ## this line is the one that breaks down on other number sets...
  y <- c(y, max(pl[[y[ly]]][!pl[[y[ly]]] %in% y]))
  y <- grow.seq(y)

  return(y)
}


## start vector
x <- 1:17

## get list of possible pairs
pl <- lapply(x, ok.pairs, vec=x)

## pick start at max since few combinations there.
y <- max(x)
grow.seq(y)
4

1 回答 1

27

您可以使用outer来计算允许的对。得到的矩阵是图的邻接矩阵，你只需要一个哈密顿路径就可以了。

# Allowable pairs form a graph
p <- outer(
  1:17, 1:17, 
  function(u,v) round(sqrt(u + v),6) == floor(sqrt(u+v)) ) 
)
rownames(p) <- colnames(p) <- 1:17
image(p, col=c(0,1)) 

# Read the solution on the plot
library(igraph)
g <- graph.adjacency(p, "undirected")
V(g)$label <- V(g)$name 
plot(g, layout=layout.fruchterman.reingold)

哈密​​顿路径

于 2012-04-14T03:40:47.343 回答