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.

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). ?

[Matt J]

The fact that you have repetitions of 1's,2's, and 3's seems not to matter, since repeated numbers are treated as distinct. You could equally well suppose that all the numbers in L are unique.

[Catalytic]

I think the repeated numbers are supposed to be treated as indistinct for the purposes of building pairs. For example, if we label the different 1's as 1a,1b,1c,1d then -

PL2=[ [1a,1b]; [1c,2];  [1d,3];  [2,2];  [2,3];  [3,3] ]

and -

PL3=[ [1c,1d]; [1a,2];  [1b,3];  [2,2];  [2,3];  [3,3] ]

are not to be considered distinct lists.

[Gilbert Hawkins]

Yes, Matt and Catalytic, the comment by Catalytic correctly identifies my intent. I intended the repeated 1s in L= [1 1 1 1 2 2 2 2 3 3 3 3] to be considered as indistinct in forming pairs, as well as the repeated 2s and 3s.

So Catalytics observation that I would consider PL3=[ [1c,1d]; [1a,2]; [1b,3]; [2,2]; [2,3]; [3,3] ] as not distinct from PL2=[ [1a,1b]; [1c,2]; [1d,3]; [2,2]; [2,3]; [3,3] ] is what I intended, assuming 1a, 1b, 1c, and 1d would be treated as indistinct.

I was assuming that if the value of two elements in a list of integers was the same, they would be regarded as indistinct, but I am probably using the wrong language in saying that.

Perhaps in the example with a list of 12 elements, I should have referenced 12 items (all of the same class) divided into three groups. The four items in each group are intended to be indistinguishable from one another, but any item from one group is distinguishable from any item in another group. Perhaps L=[A, A, A, A, B, B, B, B, C, C, C, C] would have been a better example. A list of pairs might be represented by a 2d array of 6 rows and 2 columns [ [A,A];[A,A];[B,B];[C,C];[B,C];[B,C] ] in which each row represents a pair. The list represented by the 2d array would not be made into a distinct list if the two elements in any row were interchanged (for example the fifth row of the 2d array could be [C,B] rather than [B,C] ) nor would the list represented by the 2d array be made distinct by interchanging the order of the rows. So [ [B,B];[C,C];[B,C];[B,C];[A,A];[A,A] ] would not be distinct from [ [A,A];[A,A];[B,B];[C,C];[B,C];[B,C] ]. But it would be distinct from [ [A,B];[A,A];[B,A];[C,C];[B,C];[B,C].

[Matt J]

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]

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

Answer 1

[Matt J]

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

[Gilbert Hawkins]

That's a clever, efficient script, Matt, using repmat. Your observation on the cubic dependence of the number of lists on j is very interesting. Polynomic! Thank you.

I just want to be sure I understand the output format. I believe that for different k, the value of S is loaded into sequence{k} and eventually the routine will exit and the last k is the number of lists. Each list is sequence{k} for different ks. Is that correct?

If so, I think the arguments of the repmats need to depend on k, else all calculations for S are the same for any value of k. Am I missing something? It runs fine but delivers the same S and sequence{k} for all k inserted into the line k=0 at the start.

You've been a great help on this and I will sign off soon, strongly supporting your answers. But I'm guessing one of your scripts delivers distinct lists for different ks.

[Matt J]

I'm not sure I understand the questions about k. The output should be a 3j/2-by-2-by-m array where m is the number of lists and each page sequence(:,:,i) is a different list. You should not be manipulating k at all.

Here are the first two lists that I obtain with j=6. You can see that they are different. If this is not the result you get, make sure you have my most recent post.

>> sequences(:,:,1)

ans =

1 3

1 3

1 3

1 3

1 3

1 3

2 2

2 2

2 2

>> sequences(:,:,2)

ans =

1 2

1 3

1 3

1 3

1 3

1 3

2 2

2 2

2 3

[Gilbert Hawkins]

HI Matt,

I had copied an earlier version of your script that didn't have the 3 end statements and accidentally put one in the wrong spot, so all I got was the first list. Sorry.

I have now copied your later code (shown below from my workspace) along with its response to the size of sequences(:,:,2). 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. This may be because my MatLab verson 2020A will not accept height, so I used size(s13,1), as you can see below. Is that what the trouble is?

code named FromMat2 run on my PC:

tic;

sequences=getSequences(100);

toc;

whos sequences

functionsequences=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);

remainingThrees=j-size(s13,1);

ifremainingThrees<remainingTwos, continue; end

s23=repmat([2,3],remainingTwos,1);

remainingThrees=remainingThrees-remainingTwos;

ifisodd(remainingThrees), continue; end

s33=repmat([3,3],remainingThrees/2,1);

k=k+1;

%k % 66351 last print out

S=[s11;s12;s13;s22;s23;s33];

size(S);

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

Results from running the above program on my PC ver 2020A using j=4:

>> FromMat2

Elapsed time is 1.197939 seconds.

Name Size Bytes Class Attributes

sequences 150x2x66351 159242400 double

>> size(sequences(:,:,1))

ans =

150 2

>> j

j =

4

We're getting close and I do really appreciate you help, Matt.

Using j=4, I calculated "by hand" 15 distinct lists of pairs shown below as as 15 columns. I think this is the correct answer for j=4, but I could have missed some. Below that array is the count of the number of pairs of ones, the number of pairs of twos, and the number of pairs of threes for each column.

I would love to be able to run your script and the results below for j=4 or corrections to it. For larger js, the j^3 scaling you found is very interesting but a working script is essential. Best -Gil

EachColumnOrderedPairList_jequal4 I believe these are the correct pair lists for j=4

12 11 11 11 11 22 11 12 11 21 12 11 11 21 11

12 11 11 11 22 22 12 12 12 22 12 12 13 21 12

13 22 22 23 22 31 12 12 13 23 12 13 13 22 12

13 22 23 23 31 31 22 12 23 31 31 22 22 31 32

23 33 23 23 31 31 33 33 23 31 32 23 23 31 32

23 33 33 23 33 31 33 33 23 31 33 33 23 33 33

NumberofPairsofOnesTwosandThrees in each column above

0 2 2 2 1 0 1 0 1 0 0 1 1 1 0

0 2 1 0 2 2 1 0 0 1 0 1 1 0 1

0 2 1 0 1 0 2 2 0 0 1 1 0 1 1

[Matt J]

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]

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