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.
7 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Gilbert Hawkins
el 25 de Mayo de 2024
Comentada: Gilbert Hawkins
el 30 de Mayo de 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 comentarios
Matt J
el 27 de Mayo de 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.
Respuesta aceptada
Matt J
el 28 de Mayo de 2024
Editada: Matt J
el 28 de Mayo de 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 comentarios
Matt J
el 29 de Mayo de 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.
Más respuestas (0)
Ver también
Categorías
Más información sobre Characters and Strings en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!