<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On Sep 13, 2010, at 1:34 PM, Phil Bewig wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">Do you know a better way to shuffle a list than to convert it to a vector, shuffle in place, then convert back to a list?  You might look at this discussion: <a href="http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec">http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec</a>.  The list-vector-list method is O(n); any functional method appears to be O(n log n).<br></span></font></div></blockquote><div><br></div>In fact, ANY method to do this (even with a vector) takes Omega(n log n) time.  It needs to be able to produce any of n! different answers, so it needs to make at least log(n!) decisions, which is Theta(n log n).  Otherwise there wouldn't be enough leaves on the decision tree.</div><div><br></div><br><div> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Stephen Bloch</div><div><a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a></div></div></span></span> </div> <br></body></html>