# 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)

Show older comments

Gilbert Hawkins
on 25 May 2024 at 21:27

Commented: Gilbert Hawkins
on 30 May 2024 at 0:07

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
on 27 May 2024 at 18:26

### Accepted Answer

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;

whos sequences

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

### More Answers (0)

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!