Clear Filters
Clear Filters

I want all possible distinct lists of the pairs of the elements that can be made from a vector having j ones, j twos, and j threes where j is an even integer.

90 views (last 30 days)
I have a list L of integers comprising j ones, j twos, and j threes, where j is an even integer. For example, if j=4, then the list could be L= [1 1 1 1 2 2 2 2 3 3 3 3] of length 3*j=12. I want to make distinct lists PLi, i = 1,2,….m (i and m are integers) showing various ways to pair the elements of L, using each element from L once and only once. Since there are 3*j elements in L, each PLi will have 3*j/2 pairs. The question is how many distinct lists PLi can be made if the order of the two elements in a pair is immaterial and if the order in which the pairs are listed in each PLi is immaterial. For example, one pair list, call it PL1, could be PL1 = [ [1,1]; [1,1]; [2,3]; [2,2]; [2,3]; [3,3] ] where the pairs are separated by semi-colons. The pair list [ [2,2]; [1,1]; [1,1]; [3,2]; [3,2]; [3,3] ] would not be distinct from PL1, but the pair list PL2=[ [1,1]; [1,2]; [1,3]; [2,2]; [2,3]; [3,3] ] would be distinct.
Is there a MatLab routine/command which, given L, returns all possible distinct lists of 3*j/2 pairs made from L? If not, is there an efficient algorithm to calculate all possible distinct lists PLi for large j or to estimate the dependence of the number of distinct lists (m) on the value of j?
Such a routine/command might be regarded as in the same class as nchoosek(L,2). ?
  5 Comments
Matt J
Matt J on 27 May 2024 at 18:26
It might be advisable for you to describe your ultimate purpose with this. Are you trying to generate all these lists only to enable an exhaustive search in some optimization problem? That's usually the wrong way to go about things.
Gilbert Hawkins
Gilbert Hawkins on 27 May 2024 at 20:48
Hi Matt,
No, my desire to generate these lists may surprise you. I'm a physicist (definitely not a computer scientist) who loves model trains. The unique lists of pairs with j=4 is used to create all operationally unique train layouts that can be made with 4 train switches. (Each train switch has three branches, call them A, B, and C, which is the origin of the number 3 ).
A layout having 4 switches is made from a collection of 6 track segments, with each segment having each of its ends labeled either A, B, or C. Assume L = [A A A A B B B B C C C C]. A full track segment would be characterized as a pair of elements, say (A,B) or (A,A), or (C,A), equivalently the notation could be (1,2), (1,1), and (31), meaning that that track segment would be used to connect branch A of some switch to branch B of some switch, etc. All layouts having 4 switches are made from a collection of 6 such track segments.There are only a relatively small number of such collections of 6 segments. That is where the criteria for "distinct" collections arises. (I think the example I sent in my comments showing 10 distinct lists of pairs in a 2d matrix illustrates visually what I mean by distinct.) Obviously, in any collection the labels on the ends of the 6 segments must comprise 4 As, 4Bs, and 4Cs in order that they can be used to connect all of the switches.
Many layouts can be made from any one such collection of 6 segments, but that process is fairly straight forward and yields visual pictures of train layouts. If you're a model train fan, let me know!
I do thank you for your note on the N!.. formula and its large N limit. But removing duplicate layouts is non trivial for large N. I was hoping that there might be some MatLab command a bit like nchoosek that would make all lists of 6 pairs (i.e. lists of six track segments in a layout) and that some sequence of unique( ) operators could be applied to reduce duplicates. I would love to see a pseudo code that would create my 2d array from L.
The answer to my original question may be that there is no easy command to do that in MatLab and no very efficient algorithm for large numbers of switches. It is interesting to model hobbyists, that for even a dozen switches, the number of functionally different train layouts is enormous.
All comments are much appreciated. Again, my sincere thanks! -Gil

Sign in to comment.

Accepted Answer

Matt J
Matt J on 28 May 2024 at 1:36
Edited: Matt J on 28 May 2024 at 1:52
This code doesn't seem to do too badly. I can easily run up to j=100. As you can see from the loop limits, I find the number of lists is roughly cubic in j.
tic;
sequences=getSequences(100);
toc;
Elapsed time is 0.527203 seconds.
whos sequences
Name Size Bytes Class Attributes sequences 150x2x66351 159242400 double
function sequences=getSequences(j)
isodd=@(a)logical(bitget(uint64(abs(a)),1));
k=0;
sequences=cell(1,j^3/4);
for n=0:j/2
s11=repmat([1,1],n,1);
for p=0:j-2*n
s12=repmat([1,2],p,1);
s13=repmat([1,3],(j-2*n-p),1);
for q=0:(j-p)/2
s22=repmat([2,2],q,1);
remainingTwos=j-2*q-p;
remainingThrees=j-height(s13);
if remainingThrees<remainingTwos, continue; end
s23=repmat([2,3],remainingTwos,1);
remainingThrees=remainingThrees-remainingTwos;
if isodd(remainingThrees), continue; end
s33=repmat([3,3],remainingThrees/2,1);
k=k+1;
S=[s11;s12;s13;s22;s23;s33];
sequences{k}=S;
%assert(height(S)==3*j/2 & nnz(S==1)==j & nnz(S==2)==j & nnz(S==3)==j)
end
end
end
%assert(numel(sequences)<=j^3/4)
sequences=cat(3,sequences{:});
end
  5 Comments
Matt J
Matt J on 29 May 2024 at 18:16
The arrays for the various sequences look basically right, but there are many many pair repeats, so that all the sequences(:,:,m) are of size 150x2.
Not clear why you see this as a problem. That is the correct size for j=100. In your post, you said that each list should have 3j/2 pairs, which for j=100 gives 150.
Gilbert Hawkins
Gilbert Hawkins on 30 May 2024 at 0:07
You are quite correct, Matt. Like and idiot, I forgot that evaluating j on the command line had nothing to do with j in the function that ran. The program seems to work very well with remarkable efficiency. Thank you for your patience and creative answers. I will sign off with strong praise for solving a rather interesting problem in a helpful manner. Perhaps MatLab should incorporate that like their nchoose..
PS Here is the output for j=4 switches with a print to screen statement added:
>> FromMatt
Pair List for N = 4
13 12 12 12 12 12 11 11 11 11 11 11 11 11 11
13 13 12 12 12 12 13 13 12 12 12 12 11 11 11
13 13 13 13 12 12 13 13 13 13 12 12 23 22 22
13 13 13 13 13 12 22 22 23 22 23 22 23 23 22
22 22 23 22 23 33 23 22 23 23 23 33 23 23 33
22 23 23 33 33 33 23 33 23 33 33 33 23 33 33
Elapsed time is 0.018708 seconds.
Name Size Bytes Class Attributes
sequences 6x2x15 1440 double

Sign in to comment.

More Answers (0)

Categories

Find more on Characters and Strings in Help Center and File Exchange

Products


Release

R2020a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!