Path: news.mathworks.com!not-for-mail
From: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
Newsgroups: comp.soft-sys.matlab
Subject: Re: eliminate identical raws
Date: Sun, 17 Feb 2008 03:08:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 60
Message-ID: <fp88eh$7l1$1@fred.mathworks.com>
References: <27823314.1203129850043.JavaMail.jakarta@nitrogen.mathforum.org> <fp7991$656$1@fred.mathworks.com>
Reply-To: "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1203217681 7841 172.30.248.35 (17 Feb 2008 03:08:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 17 Feb 2008 03:08:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:451907


"us " <us@neurol.unizh.ch> wrote in message <fp7991$656
$1@fred.mathworks.com>...
> vladimir:
> <SNIP combinatorial evergreen...
> 
> one of the other many solutions is outlined below 
> (including the comparison with a more traditional one as 
> shown by others)...
> timing on a wintel c2.2*2.4/2gb/winxp.sp2/r2008a
> 
> us
> 
> % the data
>      a=[3,3,3,6,6,3,3,7];
> % the engine
> tic;
>      as=sum(a);
>      au=unique(a);
>      na=numel(a);
>      nu=numel(au);
>      x=cell(na,1);
>      ap=repmat({au},1,na);
>      [x{1:na,1}]=ndgrid(ap{:});
>      x=reshape(cat(na+1,x{:}),[],na);
>      xs=whos('x');
>      x=x(sum(x,2)==as,:);
>      x=x(:,end:-1:1);
> toc
> % comparison with a more traditional solution
> tic;
>      p=perms(a);
>      ps=whos('p');
>      pu=unique(p,'rows');
> toc
> % - max temp sizes and <equal>
>      disp([xs.bytes;ps.bytes;isequal(x,pu)]);
> 
> %{
> Elapsed time is 0.051470 seconds. % sol #1
> Elapsed time is 0.182210 seconds. % sol #2
>       419904 % <- x max size
>      2580480 % <- p max size
>            1 % <- res are equal
> %}
----------
  I have serious doubts about the above line

 x=x(sum(x,2)==as,:);

in your solution #1, Urs.  Suppose that array a = [1,2,3,4].  Presumably, at the 
time you do the 'whos' command, 'x' will have 4^4 = 256 rows.  Among its 
various rows will appear [1,1,4,4], [1,3,3,3], and various rearrangements of 
these, all of which have the as = 10 sum required by the above line.  Won't 
they slip through into your final x?  I would predict that 'x' in this case will 
have ten extra unwanted rows above the expected twenty four.  I think you 
need to make your rejection criterion more exacting than a simple sum of the 
original elements.

Roger Stafford