मतलाब: किसी सूची से जोड़े बनाने के संभावित तरीकों की गणना कैसे करें

Jan 20 2021

मान लीजिए कि मेरे पास लंबाई की एक सूची है 2k, कहते हैं {1,2,...,2k}2kसंख्याओं को समूहीकृत करने के संभावित तरीकों की संख्या k(अनियंत्रित) जोड़े है n(k) = 1*3* ... *(2k-1)। तो k=2, हमारे पास 2 जोड़े बनाने के तीन अलग-अलग तरीके हैं

(1 2)(3 4)

(1 3)(2 4)

(1 4)(2 3)

मैं उपरोक्त सूची बनाने के लिए मतलाब का उपयोग कैसे कर सकता हूं, अर्थात, n(k)*(2k)इस तरह का एक मैट्रिक्स बनाएं कि प्रत्येक पंक्ति 2kमें kजोड़े में संख्याओं की सूची को समूहीकृत करने का एक अलग तरीका हो ।

जवाब

LucienXhh Jan 20 2021 at 15:37
clear
k = 3;
set = 1: 2*k;
p = perms(set); % get all possible permutations
% sort each two column
[~, col] = size(p);
for i = 1: 2: col
    p(:, i:i+1) = sort(p(:,i:i+1), 2);
end
p = unique(p, 'rows'); % remove the same row
% sort each row
[row, col] = size(p);
for i = 1: row
    temp = reshape(p(i,:), 2, col/2)';
    temp = sortrows(temp, 1);
    p(i,:) = reshape(temp', 1, col);
end
pairs = unique(p, 'rows'); % remove the same row

pairs =
    
         1     2     3     4     5     6
         1     2     3     5     4     6
         1     2     3     6     4     5
         1     3     2     4     5     6
         1     3     2     5     4     6
         1     3     2     6     4     5
         1     4     2     3     5     6
         1     4     2     5     3     6
         1     4     2     6     3     5
         1     5     2     3     4     6
         1     5     2     4     3     6
         1     5     2     6     3     4
         1     6     2     3     4     5
         1     6     2     4     3     5
         1     6     2     5     3     4

जैसा कि किसी को लगता है कि मेरा पूर्व उत्तर उपयोगी नहीं है, मैं इसे पोस्ट करता हूं।

RaymondKan Jan 20 2021 at 17:35

मेरे पास जोड़े को एनुमरेट करने के लिए निम्न ब्रूट बल तरीका है। विशेष रूप से कुशल नहीं है। यह k> 9 होने पर मेमोरी प्रॉब्लम का कारण भी बन सकता है। उस स्थिति में, मैं केवल गणना कर सकता हूं लेकिन जेड नहीं बनाऊंगा और इसमें परिणाम संग्रहीत कर सकता हूं।

function Z = pair2(k)
   count = [2*k-1:-2:3];
   tcount = prod(count);
   Z = zeros(tcount,2*k);
   x = [ones(1,k-2) 0];
   z = zeros(1,2*k);
   for i=1:tcount
       for j=k-1:-1:1
           if x(j)<count(j)
              x(j) = x(j)+1;
              break
            end
            x(j) = 1;
       end
       y = [1:2*k];
       for j=1:k-1
           z(2*j-1) = y(1);
           z(2*j) = y(x(j)+1);
           y([1 x(j)+1]) = [];
       end
       z(2*k-1:2*k) = y;
       Z(i,:) = z;
   end