Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
regarding permutation

Subject: regarding permutation

From: Yihui

Date: 12 Jun, 2011 09:25:05

Message: 1 of 4

Dear matlab experts,
I have a problem regarding permutation.
Assuming that I have 11 building blocks A. to k. (see below), I’d like to combine them to create a nine-element list, e.g., u h d u u h u h d.


A. h d u
B. h d
C. h u
D. u h d
E. u h d
F. u h u
G. h u
H. u h
I. d u
J. d
K. u

But, the nine-element list must have two ‘d’, three ‘h’ and four ‘u’.
Can someone help me out on this. Thanks!

Sincerely,
Yihui

Subject: regarding random sample and permutation_question rephrasing

From: Yihui

Date: 12 Jun, 2011 14:57:04

Message: 2 of 4

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 nine-element 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

Subject: regarding random sample and permutation_question rephrasing

From: Roger Stafford

Date: 12 Jun, 2011 19:12:04

Message: 3 of 4

"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 nine-element 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!)

  Note: It is best not to make multiple postings, as you have done here, lest it annoy potential responders.

Roger Stafford

Subject: regarding random sample and permutation_question rephrasing

From: Roger Stafford

Date: 13 Jun, 2011 00:34:04

Message: 4 of 4

"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 nine-element 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*(ix-1);
 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

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us