"Roger Stafford" wrote in message <it3324$o13$1@newscl01ah.mathworks.com>...
> "Yihui" wrote in message <it2k40$j53$1@newscl01ah.mathworks.com>...
> > Dear matlab experts,
> >
> > I have a problem regarding permutation.
> > Assuming that I have 11 building blocks A. to K. (see below).
> > A. h d u
> > B. h d
> > C. h u
> > D. u h
> > E. u h d u
> > F. u h d
> > G. u h u
> > H. d u
> > J. u d
> > K d
> > L. u
> >
> > I’d like to combine them to create a nineelement list. For example, I can select E., D., D., and K. to create:
> > u h d u u h u h d.
> >
> > But, the list must have two ‘d’, three ‘h’ and four ‘u’.
> > Can someone help me out on this. Thanks!
> > Sincerely,
> > Yihui
>           
> You haven't made it plain whether for each list of u's, h's, and d's you seek all possible combinations of the blocks that will produce it or whether any one would do. Probably each list will have many possible block combinations.
>
> If it helps any, there are 9!/(2!*3!*4!) = 1260 possible lists with the prescribed numbers of each of the three letters. There should be ways of making just two 'nchoosek' calls that would give you all of these possible lists. For example, one call could give you 9!/(2!*7!) = 36 and another call could yield 7!/(3!*4!) = 35. All pairings of the two could then give the 36*35 = 1260 total combinations (provided it is done correctly!)
>
> Roger Stafford
         
Yihui, here is code that would do the first part of your problem, the generation of all possible strings of nine letters each containing the required numbers of u's, h's, and d's. No two strings should be the same.
a = 2; % no. of d's
b = 3; % no. of h's
c = 4; % no. of u's
d = a+b+c;
c1 = nchoosek(1:d,b+c); % Get d!/((b+c)!*a!) combinations
c2 = nchoosek(1:b+c,c); % Get (b+c)!/(b!*c!) combinations
m = size(c1,1);
n = size(c2,1);
v = repmat('',m*n,d);
for ix = 1:m
v1 = repmat('d',1,d);
c11 = c1(ix,:);
v1(c11) = 'h';
ixn = n*(ix1);
v(ixn+(1:n),:) = repmat(v1,n,1);
for jx= 1:n
v(ixn+jx,c11(c2(jx,:))) = 'u';
end
end
Each row of the 'v' array is one of the possible strings of 'u', 'h', 'd'. There should be 1260 rows altogether.
The second part (which I think is the harder) is finding sequences of the blocks you defined out of which these strings can be formed. I would recommend a recursive approach. For a given string, after successfully finding a block that fits, you call recursively on the same routine with the remainder of the string. You continue until either the entire string is fitted or it fails and then you back up and proceed to the next block possibility. You will have to decide in what manner you store the results.
Roger Stafford
