Thread Subject: Number of unique combinations from sets

Hello,

I'm looking for a fast method of finding all of the unique
combinations of sets of elements (assuming that all sets
are the same).

To give an example by contrast, the Matlab File Exchange
file 'allcomb' generates all unique combinations of sets of
elements assuming taht all the sets are different), so:

allcomb([1:3], [1:3])

ans =

     1 1
     1 2
     1 3
     2 1
     2 2
     2 3
     3 1
     3 2
     3 3

what I want is:

ans =

     1 1
     1 2
     1 3
     2 2
     2 3
     3 3

A short script which achieves this is (where hyps is the
outcome of interest):

x = allcomb([1:3], [1:3]);

hyps = x(1,:);
for i = 2:size(x, 1)
    t = x(i,:);
    test = perms(t);
    for j = 1:size(test,1)
        tr(j) = any(all(repmat(test(j,:),...
                size(hyps,1), 1) == hyps,2));
    end
    if sum(tr) == 0
        hyps = [hyps; x(i,:)];
    end
end

However, this process is painfully slow for large sets
(e.g., [1:900], [1:900], [1:2] takes 6 days to complete!).

Any advice on how to speed this process up or direction
towards an existing function would be greatly appreciated.

Thanks,

Dan

"Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message
<fvr755$inh$1@fred.mathworks.com>...
> Hello,
>
> I'm looking for a fast method of finding all of the
unique
> combinations of sets of elements (assuming that all sets
> are the same).
>
> To give an example by contrast, the Matlab File Exchange
> file 'allcomb' generates all unique combinations of sets
of
> elements assuming taht all the sets are different), so:
>
> allcomb([1:3], [1:3])
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 2 1
> 2 2
> 2 3
> 3 1
> 3 2
> 3 3
>
> what I want is:
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 2 2
> 2 3
> 3 3
>
> A short script which achieves this is (where hyps is the
> outcome of interest):
>
> x = allcomb([1:3], [1:3]);
>
> hyps = x(1,:);
> for i = 2:size(x, 1)
> t = x(i,:);
> test = perms(t);
> for j = 1:size(test,1)
> tr(j) = any(all(repmat(test(j,:),...
> size(hyps,1), 1) == hyps,2));
> end
> if sum(tr) == 0
> hyps = [hyps; x(i,:)];
> end
> end
>
> However, this process is painfully slow for large sets
> (e.g., [1:900], [1:900], [1:2] takes 6 days to complete!).
>
> Any advice on how to speed this process up or direction
> towards an existing function would be greatly appreciated.
>
> Thanks,
>
> Dan

You are looking for all combinations with replacement.
Check out the file COMBSREP.m at the following link:

http://www.mathworks.com/support/solutions/files/s36265/

combsrep(1:3, 2)

"Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message <fvr755$inh
$1@fred.mathworks.com>...
> Hello,
> I'm looking for a fast method of finding all of the unique
> combinations of sets of elements (assuming that all sets
> are the same).
> .......
> Dan
-------
  I believe the call

 c = nchoosek(1:n,k);

does just what you want for k numbers chosen out of 1:n

Roger Stafford

> I believe the call
>
> c = nchoosek(1:n,k);
>
> does just what you want for k numbers chosen out of 1:n
>
> Roger Stafford
>

NCHOOSEK only gives combinations *without* replacement, so
he won't get the

1 1
2 2
3 3

elements.

> You are looking for all combinations with replacement.
> Check out the file COMBSREP.m at the following link:
>
> http://www.mathworks.com/support/solutions/files/s36265/
>
> combsrep(1:3, 2)

'combsrep' will work if the sets I'm comparing are all the
same, but it lacks the functionality of 'allcomb', which
allows the sets to contain different elements.

So to give another example:

>> allcomb([1:3], [1:4])

ans =

     1 1
     1 2
     1 3
     1 4
     2 1
     2 2
     2 3
     2 4
     3 1
     3 2
     3 3
     3 4

But I need:

ans =

     1 1
     1 2
     1 3
     1 4
     2 2
     2 3
     2 4
     3 3
     3 4

I don't think I can do this with combsrep (or am I missing
something)?

Thanks for the link though (and thanks to anyone else who's
replied), combsrep looks like a useful function anway.

"Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message
<fvrc2j$rtm$1@fred.mathworks.com>...
> > You are looking for all combinations with replacement.
> > Check out the file COMBSREP.m at the following link:
> >
> > http://www.mathworks.com/support/solutions/files/s36265/
> >
> > combsrep(1:3, 2)
>
> 'combsrep' will work if the sets I'm comparing are all the
> same, but it lacks the functionality of 'allcomb', which
> allows the sets to contain different elements.
>
> So to give another example:
>
> >> allcomb([1:3], [1:4])
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 1 4
> 2 1
> 2 2
> 2 3
> 2 4
> 3 1
> 3 2
> 3 3
> 3 4
>
> But I need:
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 1 4
> 2 2
> 2 3
> 2 4
> 3 3
> 3 4
>
> I don't think I can do this with combsrep (or am I missing
> something)?
>
> Thanks for the link though (and thanks to anyone else
who's
> replied), combsrep looks like a useful function anway.

I don't understand what you are asking for then. Your
first example looked like you were selecting an item from a
set, replacing it, then selecting again.

In this example, it looks like you have two sets(1:3 and
1:4), selecting 1 item from each set. Why is [2 1] not a
valid combination then? Are you saying the second set
changes based on your selection of the first set? All
elements of the second set which are smaller than the value
of your selection in the first set disappear?

I could come up with some code that will do this, but I
don't think this is really what you want to do. Maybe you
can explain further.

> In this example, it looks like you have two sets(1:3 and
> 1:4), selecting 1 item from each set. Why is [2 1] not a
> valid combination then?

Ok, this problem came about because I was trying to find a
way to determine how many cuboids of size a x b x c will fit
into a larger cuboid of size m x n x p. For this problem, a
x b x c is equivalent to a x c x b or b x a x c, etc. So
rotation of the cuboid shape doesn't matter.

So, if I want to find all potentially valid combinations of
a x b x c that will fit into a larger shape m x n x p, then
I have to consider all combinations of the sets [1:m], [1:n]
and [1:p], but since rotation doesn't matter I need to
eliminate any combinations where a x b x c can be created by
permuting the elements in c x b x a or a x c x b or b x a x
c, etc.

Hence, I need allcomb but with the non-unique permutations
removed. So, [1 2] is valid but [2 1] is not valid because
the reversing the elements of [2 1] equals [1 2]. Does that
help at all?


> I could come up with some code that will do this, but I
> don't think this is really what you want to do. Maybe you
> can explain further.

The script listed in my original post is correct and will do
what I need, but it's incredibly slow for large set sizes.

Hope that clarifies the issue a little.

"Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message
<fvrc2j$rtm$1@fred.mathworks.com>...

OK. I guess you might want all combinations but where
order is unimportant. Playing with ALLCOMB, it is much
better than COMBSREP. Here is a quick adjustment you can
make to the output of ALLCOMB to obtain what you are
looking for:

tic
a = unique(sort(allcomb(1:900,1:900),2),'rows');
toc
Elapsed time is 0.927414 seconds.


In fact, the same author (Jos van der Geest) has a
different function called COMBN which appears to be
specific to drawing combinations from the same set (without
replacement). However, it is slowing than ALLCOMB when
given the same set:

tic
a = allcomb(1:900,1:900);
toc
Elapsed time is 0.075114 seconds.

tic
b = combn(1:900,2);
toc
Elapsed time is 0.399549 seconds.

isequal(a,b)

ans =

     1

Jos should probably just call ALLCOMB from COMBN. COMBN
just allows you to use:

combn(1:20,4)

rather than having to use:

allcomb(1:20,1:20,1:20,1:20)

"helper " <spamless@nospam.com> wrote in message
<fvrfo5$l1l$1@fred.mathworks.com>...
> "Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message
> <fvrc2j$rtm$1@fred.mathworks.com>...
>
> OK. I guess you might want all combinations but where
> order is unimportant. Playing with ALLCOMB, it is much
> better than COMBSREP. Here is a quick adjustment you can
> make to the output of ALLCOMB to obtain what you are
> looking for:
>
> tic
> a = unique(sort(allcomb(1:900,1:900),2),'rows');
> toc
> Elapsed time is 0.927414 seconds.
>


Thanks so much. I didn't think to sort the columns first
before calling unique. Good stuff.

"Daniel " <danielDOTrDOTlittle@gmail.com> wrote in message <fvr755$inh
$1@fred.mathworks.com>...
> Hello,
>
> I'm looking for a fast method of finding all of the unique
> combinations of sets of elements (assuming that all sets
> are the same).
>
> To give an example by contrast, the Matlab File Exchange
> file 'allcomb' generates all unique combinations of sets of
> elements assuming taht all the sets are different), so:
>
> allcomb([1:3], [1:3])
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 2 1
> 2 2
> 2 3
> 3 1
> 3 2
> 3 3
>
> what I want is:
>
> ans =
>
> 1 1
> 1 2
> 1 3
> 2 2
> 2 3
> 3 3
>
> A short script which achieves this is (where hyps is the
> outcome of interest):
>
> x = allcomb([1:3], [1:3]);
>
> hyps = x(1,:);
> for i = 2:size(x, 1)
> t = x(i,:);
> test = perms(t);
> for j = 1:size(test,1)
> tr(j) = any(all(repmat(test(j,:),...
> size(hyps,1), 1) == hyps,2));
> end
> if sum(tr) == 0
> hyps = [hyps; x(i,:)];
> end
> end
>
> However, this process is painfully slow for large sets
> (e.g., [1:900], [1:900], [1:2] takes 6 days to complete!).
>
> Any advice on how to speed this process up or direction
> towards an existing function would be greatly appreciated.
>
> Thanks,
>
> Dan
------------
  There is something sorely amiss with your coding if it takes six days to
cover all the combinations of the kind you want with only the sets

 [1:900], [1:900], [1:2]

There are only 1620000 different combinations altogether from these sets,
even considering all as being different. That is not very many to go through
for a computer unless you have RAM storage problems! It ought to finish up
in only a few seconds.

  I am still striving for a precise general definition of what it is you are after.
If you have set1, set2, set3, ..., setn as n sets of integers, then the integer
sequence a1, a2, a3, ..., an, should appear whenever 1) each ai belongs to
seti, and 2) if any ai and aj pair both belong to each of seti and setj, then if i
< j, we have ai <= aj. In other words any pair of integers that both come
from each of two sets should always appear in ascending order. Does that
accurately define what you are after?

  If so, I would think you could just use 'allcomb' first and subsequently delete
all those which failed this second condition. The rejection rate should not be
excessive until the number of sets gets too large.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <fvri01$ghb$1@fred.mathworks.com>...
> There is something sorely amiss with your coding if it
> takes six days to cover all the combinations of the kind
 > you want with only the sets
>
> [1:900], [1:900], [1:2]
> There are only 1620000 different combinations altogether
from these sets,
> even considering all as being different. That is not very
many to go through
> for a computer unless you have RAM storage problems! It
ought to finish up
> in only a few seconds.
 
Yes, the only way i could think to do it was to call allcomb
and then search through the output for permutations (what
the code in the first post does). Which I think would make
1620000 * 6...at any rate the script above isn't efficient
in any respects (hence, my post :-)


> I am still striving for a precise general definition of
what it is you are after.
> If you have set1, set2, set3, ..., setn as n sets of
integers, then the integer
> sequence a1, a2, a3, ..., an, should appear whenever 1)
each ai belongs to
> seti, and 2) if any ai and aj pair both belong to each of
seti and setj, then if i
> < j, we have ai <= aj. In other words any pair of
integers that both come
> from each of two sets should always appear in ascending
order. Does that
> accurately define what you are after?
>
> If so, I would think you could just use 'allcomb' first
and subsequently delete
> all those which failed this second condition. The
rejection rate should not be
> excessive until the number of sets gets too large.

Yes, I think you're description is correct. Certainly, the
method you describe for finding a solution works and is
essentially what's happening when you call...

a = unique(sort(allcomb(1:a, 1:b, 1:c), 2), 'rows);

I had forgotten about the sort function and all I could
remember was sortrows, which obviously doesn't do what is
needed. Thanks for you help.

"helper " <spamless@nospam.com> wrote in message
<fvrfo5$l1l$1@fred.mathworks.com>...
...

>
> Jos should probably just call ALLCOMB from COMBN. COMBN
> just allows you to use:

Thanks for this suggestion.

Jos