generating large, non-repeating, color palates for world maps

I am mapping regions generated using k-means clustering of ecological 
variables at a global scale. I need to generate large random color ramps 
(200 and 500 colors, for example) that do not repeat and implement them 
in such a way as to minimize adjacency of similar colors. I am 
generating my plots using spplot.

Currently, I generate my color ramps using rainbow() with the number of 
categories in the spplot call as follows:

#df is a sp object of all land surface at .5 degree resolution. I am 
mapping df$clusternum, a category that ranges from 1-n, where n is the 
number of clusters.

n<-200
spplot(df,zcol="clusternum",col.regions=rainbow(n,start=1/6,end=1),at=0:n)

Is there a better way to do this where I can a.) randomize the colors 
and b.) minimize adjacency of similar colors?

Thank you.

-Damian