Thread Subject: How can I do this in MATLAB? (Possibilities)

Hello,
Say I have an vector a=[0 0 0]; I want all the possibilities of switching the zeros to numbers. For example I want a function that grants the following as output:

Number of zeros: 3
Max number sum: 3

Output:
0 0 0
1 0 0
0 1 0
0 0 1
2 0 0
1 1 0
0 2 0
0 1 1
0 0 2
1 0 1
3 0 0
2 1 0
2 0 1
0 3 0
1 2 0
0 2 1
0 0 3
0 1 2
1 0 2
1 1 1

Or at least get the answer for maximum sum of 1:
0 0 0
1 0 0
0 1 0
0 0 1

I think I can do it using dec2bin and some other operations but it would be extremely inefficient.
Any help is welcome!

On 31 Jan, 15:19, "Husam Aldahiyat" <numand...@gmail.com> wrote:
> Hello,
> Say I have an vector a=[0 0 0]; I want all the possibilities of switching the zeros to numbers. For example I want a function that grants the following as output:
...
> I think I can do it using dec2bin and some other operations but it would be extremely inefficient.

Homework?

Seems to be a combination of number theory and combinatorics.
I'd go for a solution that takes the remaining number of
digits and remaning available sum as argument, and recursively
traverses the digit positions.

Since this is a combinatoric problem, don't be expected
if the solution requires an algorithm of high complexity;
something like D^S (or worse) where D is the number of
digits and S is the sum.

Rune

"Husam Aldahiyat" :
If you want to stay simple and not get too fancy, just do three nested for loops. Pretty simple.

"Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm1mkl$eq0$1@fred.mathworks.com>...
> Hello,
> Say I have an vector a=[0 0 0]; I want all the possibilities of switching the zeros to numbers. For example I want a function that grants the following as output:
>
> Number of zeros: 3
> Max number sum: 3
>
> Output:
> 0 0 0
> 1 0 0
> 0 1 0
> 0 0 1
> 2 0 0
> 1 1 0
> 0 2 0
> 0 1 1
> 0 0 2
> 1 0 1
> 3 0 0
> 2 1 0
> 2 0 1
> 0 3 0
> 1 2 0
> 0 2 1
> 0 0 3
> 0 1 2
> 1 0 2
> 1 1 1
>
> Or at least get the answer for maximum sum of 1:
> 0 0 0
> 1 0 0
> 0 1 0
> 0 0 1
>
> I think I can do it using dec2bin and some other operations but it would be extremely inefficient.
> Any help is welcome!

  I don't think 'dec2bin' would be of much use to you. Instead, let n be the number of "zeros" and m the maximum sum, and do this:

 output = diff([zeros(nchoosek(n,n+m),1),nchoosek(1:n,n+m)])-1;

The output should be an (n+m)!/(n!*m!) by n array containing all the possibilities that you have listed, though not in the sequential order you have used.

Roger Stafford

Thanks for the reply and no, it's not homework; it's part of a larger algorithm I'm working on.
Anyway I figured it out. It's a bit messy but good enough for my application.

function sS=eiiy(var,ord)
co=zeros(1,var);
c=1;
CC=zeros(1,var);
for h=1:ord;
for k=1:var
CC(c,:)=co;
CC(c,k)=CC(c,k)+h;
for g=[1:k-1 k+1:var]
for p=0:h
CC(c,g)=p;
CC(c+1,:)=CC(c,:);
c=c+1;
end
CC(c,:)=co;
CC(c,k)=CC(c,k)+h;
end
end
end
CCR=unique(CC,'rows');
qr=sum(CCR,2);
sS=CCR(qr<=ord,:);
end

Example:
>> eiiy(3,4)

ans =

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

I think it works for all cases.

Forget my last post the code is still incomplete.
Roger Stafford, your code doesn't work because n+m is larger than n.

A brute force approach would be to find all the permutations (NOT combinations) then filter it.

http://www.mathworks.com/matlabcentral/fileexchange/11462


vct = npermutek([0 1 2 3],3);
idx = find(sum(ans,2)<=3);
vct = vct(idx,:)

vct =

     0 0 0
     0 0 1
     0 0 2
     0 0 3
     0 1 0
     0 1 1
     0 1 2
     0 2 0
     0 2 1
     0 3 0
     1 0 0
     1 0 1
     1 0 2
     1 1 0
     1 1 1
     1 2 0
     2 0 0
     2 0 1
     2 1 0
     3 0 0





8[T[ia_[Thy^ThXgTr\lraLXgbrVrU@brbrTX!XrgcUT\T`-rbZ_yV`3cbb

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gm1prp$95f$1@fred.mathworks.com>...
> I don't think 'dec2bin' would be of much use to you. Instead, let n be the number of "zeros" and m the maximum sum, and do this:
>
> output = diff([zeros(nchoosek(n,n+m),1),nchoosek(1:n,n+m)])-1;
>
> The output should be an (n+m)!/(n!*m!) by n array containing all the possibilities that you have listed, though not in the sequential order you have used.
>
> Roger Stafford

  My apologies! I got the arguments backwards in 'nchoosek'. It should be

 output = diff([zeros(nchoosek(m+n,n),1),nchoosek(1:m+n,n)])-1;

  Also I have assumed here that matlab always returns each combination from 'nchoosek' in ascending order from 1:m+n. However Mathworks' documentation makes no such promise. If it turns out to be untrue, you would have to do a sort on the rows of its output.

 output = diff([zeros(nchoosek(m+n,n),1),sort(nchoosek(1:m+n,n),2)])-1;

Roger Stafford

Roger Stafford:
Code still doesn't work.

Matt Fig:
Thanks a lot, just what I needed.

"Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm1t2t$3eh$1@fred.mathworks.com>...
> Roger Stafford:
> Code still doesn't work.
> ......

  Yes, you are quite right, Husam. I didn't use 'diff' correctly. It is intended to operate on the rows from 'nchoosek'. Try this:

 output = diff([zeros(nchoosek(m+n,n),1),nchoosek(1:m+n,n)],1,2)-1;

  And as I mentioned, you might need to use the sort, though I suspect not.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gm1u0v$3df$1@fred.mathworks.com>...
> "Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm1t2t$3eh$1@fred.mathworks.com>...
> > Roger Stafford:
> > Code still doesn't work.
> > ......
>
> Yes, you are quite right, Husam. I didn't use 'diff' correctly. It is intended to operate on the rows from 'nchoosek'. Try this:
>
> output = diff([zeros(nchoosek(m+n,n),1),nchoosek(1:m+n,n)],1,2)-1;
>
> And as I mentioned, you might need to use the sort, though I suspect not.
>
> Roger Stafford

Amazing. I can't believe you write codes from your mind without testing them.
This is what I was *really* looking for, thanks!

In article <gm1uut$335$1@fred.mathworks.com>,
Husam Aldahiyat <numandina@gmail.com> wrote:
>Amazing. I can't believe you write codes from your mind without testing them.
>This is what I was *really* looking for, thanks!

Maybe Roger tests them in his mind too (some people are like
that apparently). Anyway, I agree it's impressive. :-)

Francis

"Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm1uut$335$1@fred.mathworks.com>...
> Amazing. I can't believe you write codes from your mind without testing them.
> This is what I was *really* looking for, thanks!

  Sorry about that, Husam! (Blush!)

  To compensate for that, I will expound on the theoretical aspects of that algorithm. Is is fairly easy to show that for each one of the combinations churned out by nchoosek(1:m+n,n), provided it is in ascending order (which obviously it can be placed in by 'sort' if necessary,) the processing with the 'diff' and subtraction by 1, maps each combination uniquely onto one of your number sets. A different combination must necessarily lead to a different number set.

  On the other hand, if you add 1 to any of your number sets, and then do a 'cumsum', you are bound to arrive back at a unique combination of ascending numbers from 1:m+n. A different number set will always lead to a different subsequence of 1:m+n - that is to say, a combination which is in ascending order. Since this is the inverse of the "diff" mapping, this shows that we have a one-to-one mapping of all combinations onto all of your kind of sets for any given m and n.

  That establishes the validity of the algorithm and the fact that there are exactly (m+n)!/(n!*m!) of your different number sets.

Roger Stafford

Roger,

Thank you for providing that algorithm, I am still trying to fully understand it. For example, how would you modify it for m~=n? For example,

m = 3;
n = 2; % or
%m = 3;
%n = 4;

vct = npermutek(0:m,n);
vct = vct(sum(vct,2)<=n,:);




gh8Ye`2eY]gwg[mwww&daw~EZ_qYnYYlfw`mZfl]whY`~c=]]agg[YQwdgl

Matt Fig:
The code works for all choices.
>> m=3

m =
     3

>> n=2

n =
     2

>> output = diff([zeros(nchoosek(m+n,n),1),nchoosek(1:m+n,n)],1,2)-1

output =

     0 0
     0 1
     0 2
     0 3
     1 0
     1 1
     1 2
     2 0
     2 1
     3 0

Roger Stafford:
Thanks for the explanation, I now understand how it works. I didn't get the second paragraph though but I'll reread it and keep trying it out until I do. Thanks a heap!

"Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm3c89$7dg$1@fred.mathworks.com>...
> Matt Fig:
> The code works for all choices.


Oh, I see now I was mixing the m and n in Roger's code. Thanks





5dkb\^\ctijjz\o)]iqgfHz\zjj"oh\`j"@]\`zz`kcdoppzhg\c^T;zzj`

"Matt Fig" <spamanon@yahoo.com> wrote in message <gm2up1$beg$1@fred.mathworks.com>...
> Roger,
>
> Thank you for providing that algorithm, I am still trying to fully understand it. For example, how would you modify it for m~=n? For example,
>
> m = 3;
> n = 2; % or
> %m = 3;
> %n = 4;
>
> vct = npermutek(0:m,n);
> vct = vct(sum(vct,2)<=n,:);

  Yes, Matt, your code would work if you replaced n with m in the second line, n being the number of elements and m being the maximum size:

 vct = npermutek(0:m,n);
 vct = vct(sum(vct,2)<=m,:);

  However, it is important to note that while this is a reasonable way to do the problem for small m and n, it becomes somewhat inefficient for larger numbers. For example, if m = 6 and n = 9, 'npermutek' would generate (m+1)^n = 7^9 = 40353607 rows to begin with, but after the second line is executed, only 15!/6!/9! = 5005 would remain, which is only about one in each eight thousand. If 'nchoosek' is used, all 5005 rows produced are utilized. It seems the natural way to do this problem.

  As for understanding the algorithm using 'nchoosek', once the notion of the natural one-to-one correspondence prevailing between the (hopefully) ordered n-element subsequences of 1:m+n from 'nchoosek' with the sets as defined by Husam, is grasped, then everything falls into place. The 'diff' and subtraction by 1 does the mapping in one direction and addition of 1 followed by cumsum maps in the reverse direction. The two kinds of number sets are in this sense equivalent even though they seem very different at first glance.

  However, if the combinations selected by nchoosek(1:m+n,n) are not chosen as the ascending subsequences, then it becomes far less efficient, since it would require a massive sort operation on the output of 'nchoosek'. My impression is that a sort is not required, but MathWorks' documentation doesn't seem to actually specify what orderings are given to its generated combinations.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message

> However, it is important to note that while this is a reasonable way to do the problem for small m and n, it becomes somewhat inefficient for larger numbers. For example, if m = 6 and n = 9, 'npermutek' would generate (m+1)^n = 7^9 = 40353607 rows to begin with, but after the second line is executed, only 15!/6!/9! = 5005 would remain, which is only about one in each eight thousand. If 'nchoosek' is used, all 5005 rows produced are utilized. It seems the natural way to do this problem.


Oh yes, I am painfully aware of the inefficiency of such a brute force technique for large numbers, that's why I called it such and mentioned the need to filter it in my first post :).
I think the beauty of the solution you proposed is precisely that it doesn't require any filtering, that is why I am trying to understand it, I may find it useful for other applications.
I am not sure it is due to a lack of explanation on your part, it may just be a one of those things I have to see for myself through sudden insight, but I don't understand why this works. I DO believe it works, I just don't see the part where you said, "It is fairly easy to show that ... each one of the combinations churned out by...maps each combination uniquely..."
 
Anyway, thanks again for posting this, I think it is one of the neatest snippets I have seen on the newsgroup in a while!




&00$|A{{( g*{Z+//{#{*)}:|})*"/#H('4 {:: *#:Ts:: +{_:'A$**:1

"Matt Fig" <spamanon@yahoo.com> wrote in message <gm4b2j$1f2$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message
> .......
> I DO believe it works, I just don't see the part where you said, "It is fairly easy to show that ... each one of the combinations churned out by...maps each combination uniquely..."
> .......

  Perhaps I can make all that a little clearer, Matt and Husam. Suppose we first start with one of Husam's number sets h(1:n) where

 0 <= h and sum(h) <= m

and all h's are integers. Now add one to each of them, H = h + 1. We still have integers and now

 1 <= H and sum(H) <= m + n

because we added a total of n ones to the sum. Next do c = cumsum(H). We then have that

 1 <= c(1) < c(2) < c(3) < ... < c(n) = sum(H) <= m+n

where all c's are still integers. This demonstrates that the resulting c is one of the n-element subsequences of 1:m+n.

  Now turn things around. Start with an arbitrary n-element subsequence of 1:m+n. Call it c. It must have the property

 1 <= c(1) < c(2) < c(3) < ... < c(n) <= m+n

Then do H = diff([0,c]) so that H(1) = c(1), H(2) = c(2)-c(1), etc. We have H >= 1 for all H's and sum(H) = c(n) <= m+n. Finally we do h = H-1 and find that we have the property

 0 <= h and sum(h) <= m

which makes it a valid Husam set.

  Moreover it is clear that these two operations from h to c and back are inverses of one another. This means the above has established a one-to-one mapping between the class of all subsequences of 1:m+n and the class of all Husam (pardon me for stealing your name Husam) sets with given m and n. The classes are therefore equal in cardinality and this transformation gets us from members of the one to unique members of the other.

  Here's a concrete example. Let n = 9 and m = 6 and suppose we start with a legitimate Husam set:

 h = [0 2 0 1 0 0 0 0 1]. We get
 H = h + 1 = [1 3 1 2 1 1 1 1 2] and
 c = cumsum(H) = [1 4 5 7 8 9 10 11 13]

which is a subsequence of 1:15. Then work backwards:

 h = diff([0,c]) = [1 3 1 2 1 1 1 1 2] and
 c = h - 1 = [0 2 0 1 0 0 0 0 1]

which is the original Husam set right where we started.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message

> Wonderful explanation....


Thanks Roger, that really clears it up. Now one last question (or two), how in the wold did you see that before hand? Was this something you discovered long ago and are now applying, or did you just see the pattern and have a flash of insight? Thanks in either case.




RSOKMSZY^RYY^iYCQiK_ZKKiUW$/Ki`KiY^ci*RVYO_pOXLM7VKpwLWOXii

"Matt Fig" <spamanon@yahoo.com> wrote in message <gm4uqd$84d$1@fred.mathworks.com>...
> Thanks Roger, that really clears it up. Now one last question (or two), how in the wold did you see that before hand? Was this something you discovered long ago and are now applying, or did you just see the pattern and have a flash of insight? Thanks in either case.

  Well, you are placing a strain on my poor octogenarian memory. I did a pen and paper calculation of the counts of Husam's sets for a couple of different cases for small m and n, and saw that they agreed with the formula (m+n)!/m!/n! and then said "Aha!". I had a vague recollection from long ago of some other class of seemingly unrelated objects being found to be in one-to-one correspondence with the class of combinations. I can't remember now what it was, but it differed from this.

  I suppose you can say the "flash of insight" came in stumbling onto the right connection involving the 'diff' action to map subsequences (ordered combinations) onto "Husam" sets and visa versa, but it certainly helped to realize that there surely ought to exist some such relationship. It only had to be discovered.

Roger Stafford

On Jan 31, 9:19=A0am, "Husam Aldahiyat" <numand...@gmail.com> wrote:
> Hello,
> Say I have an vector a=3D[0 0 0]; I want all the possibilities of switchi=
ng the zeros to numbers. For example I want a function that grants the foll=
owing as output:
>
> Number of zeros: 3
> Max number sum: 3
>
> Output:
> 0 0 0
> 1 0 0
> 0 1 0
> 0 0 1
> 2 0 0
> 1 1 0
> 0 2 0
> 0 1 1
> 0 0 2
> 1 0 1
> 3 0 0
> 2 1 0
> 2 0 1
> 0 3 0
> 1 2 0
> 0 2 1
> 0 0 3
> 0 1 2
> 1 0 2
> 1 1 1
>
> Or at least get the answer for maximum sum of 1:
> 0 0 0
> 1 0 0
> 0 1 0
> 0 0 1
>
> I think I can do it using dec2bin and some other operations but it would =
be extremely inefficient.
> Any help is welcome!

Here's an exercise utilizing arrayfun() and feval():

feval(@(m) m(arrayfun(@(i)sum(m(i,:))<=3D3,1:size(m,1)),:),cell2mat
(arrayfun(@(x)cell2mat(arrayfun(@(y)cell2mat(arrayfun(@(z) [x,y,z],
0:3,'UniformOutput', false)'),0:3,'UniformOutput', false)'),
0:3,'UniformOutput', false)'))

output:

ans =3D

     0 0 0
     0 0 1
     0 0 2
     0 0 3
     0 1 0
     0 1 1
     0 1 2
     0 2 0
     0 2 1
     0 3 0
     1 0 0
     1 0 1
     1 0 2
     1 1 0
     1 1 1
     1 2 0
     2 0 0
     2 0 1
     2 1 0
     3 0 0

This approach can apply for some more flexibility at times.