Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!e21g2000yqe.googlegroups.com!not-for-mail From: Derek <derekroconnor@eircom.net> Newsgroups: comp.soft-sys.matlab Subject: Re: Derangement: efficient full permutation Date: Sun, 6 Feb 2011 07:58:17 -0800 (PST) Organization: http://groups.google.com Lines: 106 Message-ID: <590b82f4-743b-41f3-a43c-10ea68a644ce@e21g2000yqe.googlegroups.com> References: <ii8ut8$3fb$1@fred.mathworks.com> <ii90lg$qmd$1@fred.mathworks.com> <f2e6f497-12cb-4a5a-91e6-3864562cd15a@k7g2000yqj.googlegroups.com> <iiklnk$pvl$1@fred.mathworks.com> NNTP-Posting-Host: 86.46.194.51 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1297007897 29748 127.0.0.1 (6 Feb 2011 15:58:17 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sun, 6 Feb 2011 15:58:17 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: e21g2000yqe.googlegroups.com; posting-host=86.46.194.51; posting-account=YfQr9QoAAABmrluCbkOyWpxHjBrK0lgY User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 6.1; en-GB; rv:1.9.2.13) Gecko/20101203 Firefox/3.6.13 GTB7.1,gzip(gfe) Xref: news.mathworks.com comp.soft-sys.matlab:708431 On Feb 5, 11:16 pm, "Jan Simon" <matlab.THIS_Y...@nMINUSsimon.de> wrote: > Dear Derek, > > Thanks for your answer. > > > I then testedJan'sGRDsimon for various n=5,6,7,8,9,10 and found it > > is flawed. [...] > > This shows that not all permutations generated by GRDsimon are > > derangements. > > No doubt, my approach is flawed. But I cannot reproduce a non-derangement permutation. Although this is surprising to me, it is not worth to discuss if my approach is "more correct" than you assume, as long as it is less than correct. > > Kind regards,Jan Jan, I'm re-posting this because after 6 hours it has tot appeared. POSTED to CSSM Sunday, February 6, 2011 10:26 Dear Jan, Mea culpa, mea culpa, mea maxima culpa! Everything I said in my previous post is complete rubbish, but let it stay there as a lesson. In error I was using for k = 2:n. When I changed this to your for k = 1:n then p = GRDsim(n) worked perfectly in all the tests I have done on it so far. Here are some typical results ------------------------------------------------------------------------------- >> n=10; target = GRDrej(n); [p,k,t] = FindGRDrejr(target, 3); Starting search for [6 3 1 9 4 8 5 10 2 7] Target FOUND after k = 1040194 iterations. Time = 23.0014 secs. Fraction of Space searched (k/n!) = 0.28665 Rate = 45224 permutations per second Target and last p generated: 1 2 3 4 5 6 7 8 9 10 6 3 1 9 4 8 5 10 2 7 6 3 1 9 4 8 5 10 2 7 GRDsim generated number of permutations = 1040194 Generated number of derangements = 1040194 Frac. of total = 1 Expected number of derangements = 1040194 Generated number of cyclic permutations = 234379 Frac. of total = 0.22532 Expected number of cyclic permutations = 282755 Number of random numbers generated = 11888239 Frac. of min. = 1.1429 -------------------------------------------------------------------------------- As you can see, all your permutations are derangements and 22.5% of them are cyclic which is about right. This suggests that your method is sampling from the complete space of derangements and is not biased. A very significant feature of GRDsim is that it uses only 1.1429 times the random numbers that GRPfys uses (based on my limited tests). This means that it is a very efficient Las Vegas rejection algorithm. Remember that GRDrej uses 2.718 and GRDmpp uses 2 times the random numbers that GRPfys uses, on average. Here are timing tests >>[times,ntimes] = TestDerangeTimes(0,[10^4 10^5 10^6],10); ------------------------------------------------------------------ Four Derangement Generators. No. Samples = 10 ------------------------------------------------------------------ n GRDrej GRDsim GRDmpp GRDmex Times (secs) ---------------------------------------------------- 10000 0.0018628 0.0016665 0.0021822 0.0020541 100000 0.016393 0.015044 0.020054 0.0072654 1000000 0.48478 0.25515 0.29849 0.19957 Normalized Times ----------------------------------------------- 10000 1.1177 1 1.3094 1.2326 100000 2.2563 2.0707 2.7601 1 1000000 2.4291 1.2785 1.4956 1 ------------------------------------------------------------------ You can see that your GRDsim is fast and even manages to beat GRDmex sometimes. If GRDsim passes further tests then I believe you have invented a very significant combinatorial algorithm. I wish I had the mathematical ability to prove its correctness and analyze its random running time. I suggest you contact Martinez et al. Regards, Derek O'Connor