Re: Second output argument for setdiff

[Jaroslav Hajek]

On Wed, Apr 16, 2008 at 12:41 PM, Marco Caliari <address@hidden> wrote:
> OK, please try the following instead
>
>  if (iscellstr (a))
>   [sorta,idxa] = sort(a(:));
>   idx = idxa(find(any(strcmp(repmat(sorta(:)',size(c,1)*size(c,2),1),...
>         repmat(c(:),1,size(a,1)*size(a,2))))));
>  else
>   [sorta,idxa] = sort(a);
>   idx = idxa(find(any(repmat(sorta(:)',size(c,1)*size(c,2),1) ==...
>         repmat(c(:),1,size(a,1)*size(a,2)))));
>  endif
>
>  [y,iy] = unique(a(idx));
>  i = reshape(idx(iy),size(c,1),length(idx(iy))/size(c,1));
>

Note that this has quadratic complexity, although it can certainly be
done in N*log(N)
by tracking the indices already when sorting.


>  with the following test
>
>  [c,i]=setdiff({"two","two";"three","four"},{"one","two";"three","six"})
>
>  i should be 4.
>
>  Marco
>
>
>
>
> > Am Dienstag, den 15.04.2008, 16:33 -0400 schrieb John W. Eaton:
> >
> > > On 15-Apr-2008, Marco Caliari wrote:
> > >
> > > | Dear maintainers,
> > > |
> > > | first of all, my apologizes for not sending a hg patch.
> > > | The following code
> > > |
> > > | [sorta,idxa] = sort(a);
> > > | idx = idxa(find(all(repmat(sorta(:)',size(c,1)*size(c,2),1)-...
> > > |        repmat(c(:),1,size(a,1)*size(a,2))) == 0));
> > > | [y,iy] = unique(a(idx));
> > > | i = reshape(idx(iy),size(c,1),length(idx(iy))/size(c,1));
> > > |
> > > | put at the end of setdiff.m (Octave 3.0.1b) will return i such that c
> =
> > > | a(i) (or c = a(i,:)). I checked the behaviour vs. Matlab with the
> following
> > > | script
> > > |
> > > | clear all
> > > | disp('easy')
> > > | a = [10 20 30 40]
> > > | b = [20 40]
> > > | [c,i] = setdiff(a,b)
> > > | disp('unsorted')
> > > | a = [40 20 30 10]
> > > | b = [20 40]
> > > | [c,i] = setdiff(a,b)
> > > | disp('double entries')
> > > | a = [40 40 20 30 10]
> > > | b = [20 40]
> > > | [c,i] = setdiff(a,b)
> > > | disp('rows')
> > > | A = [10 20;30 40;50 60;30 40];
> > > | B = [10 20];
> > > | [C,I] = setdiff(A,B,'rows')
> > > |
> > > | It would be nice to have this feature included in the next Octave
> release.
> > >
> > > Would someone please turn this into a patch that includes tests?
> > >
> >
> > Not possible, after including the attached patch:
> >
> >
> ===============================================================================
> >
> > > test setdiff
> > >
> >  *****
> assert(setdiff({"one","two";"three","four"},{"one","two";"three","six"}),
> {"four"})
> > !!!!! test failed
> > error: binary operator `-' not implemented for `cell' by `cell' operations
> >
> ===============================================================================
> >
> > I didn't look into it further.
> >
> >        Thomas
> >
> >
>

It seems that in recent versions of Matlab, all the set functions
(intersect, union, complement, setdiff, unique etc.) support the
'rows' parameter as well as returning "track indices". I would
recommend, instead of adding random hacks like this, to do this for
the whole "set" group - the result will likely be cleaner, less
bloated and perhaps more efficient.

Unless anyone else volunteers, I can do it, but I'm somewhat busy now,
so it will take some time.

regards,



-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz