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.
4 views (last 30 days)
Show older comments
Gilbert Hawkins
on 25 May 2024
Commented: Gilbert Hawkins
on 30 May 2024
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
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.
Accepted Answer
Matt J
on 28 May 2024
Edited: Matt J
on 28 May 2024
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
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
Find more on Matrix Indexing in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!