Ordering 1:17 by perfect square pairs

r

Solution

You can use `outer` to compute the allowable pairs. The resulting matrix is the adjacency matrix of a graph, and you just want a Hamiltonian path on it.

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

Problem

There was an interesting question on R-help: "Take the numbers one up to 17. Can you write them out in a line so that every pair of numbers that are next to each other, adds up to give a square number?" My solution is below and not particularly special. I'm curious about a more elegant and/or robust solution. Maybe a solution that can take an arbitrary string of numbers and order them like this if possible? ``` 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) ```

Original source