Code Golf: Mix the nuts so that none of the same kind are touching
GolfScript, 42 41 37 38 characters
~.`{\`{=}+%1-,}+$.,)2//zip[]*.2&lt;..&amp;=*p

The code expects input on STDIN and prints result to STDOUT, e.g.:
&gt; [&quot;walnut&quot; &quot;walnut&quot; &quot;walnut&quot; &quot;macadamia&quot; &quot;pistachio&quot;]
[&quot;walnut&quot; &quot;macadamia&quot; &quot;walnut&quot; &quot;pistachio&quot; &quot;walnut&quot;]

&gt; [&quot;walnut&quot; &quot;walnut&quot; &quot;walnut&quot; &quot;macadamia&quot; &quot;walnut&quot;]
[]

The script became longer than expected but I suppose there is room for improvement.
Edit: The case of a list with a single item costs me 1 character (the best comparison I could come up with is the same as Peter's).