Đặt hàng 1:17 theo cặp hình vuông hoàn hảo

Question

Có một câu hỏi thú vị về trợ giúp R:

"Lấy số một lên đến 17. Bạn có thể viết chúng ra thành một dòng để mỗi cặp số bên cạnh nhau, thêm lên để đưa ra một số vuông? "

Giải pháp của tôi dưới đây và không đặc biệt đặc biệt. Tôi tò mò về một giải pháp thanh lịch và/hoặc mạnh mẽ hơn. Có lẽ một giải pháp có thể lấy một chuỗi số tùy ý và ra lệnh cho họ như thế này nếu có thể?

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) 

Answer 1

Bạn có thể sử dụng outer để tính toán các cặp cho phép. Ma trận kết quả là ma trận kề của biểu đồ, và bạn chỉ muốn một Hamiltonian path trên đó.

# 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)