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