生成所有組合擴展到大列

Question

我有C列，我想填補所有組合的N個元素（C> N）。我如何在Matlab中做到這一點？例如：C = 5，N = 3;那麼從1到N即1到3的N的所有組合填充在C = 5列中。我嘗試了NchooseK，但無法做到這一點。預期輸出看起來如下：

輸出：11111，11112 ， 11122， 11222， .....， 22222， 22223， 22233， .....， 33333， ..... 12312， 12313， 12323， ...等等...
通過這種方式爲N 1的所有組合充滿高達C柱。我的C可以大到40，而N可以是10.
在Matlab中有沒有什麼辦法。

Answer 1

這是一個樹遍歷問題。下面是一個方法DFS：

function s = GetCombinations(C,N) 
C = int64(C); 
N = int64(N); 
assert(C>0 && N>0, 'Invalid input') 
s = prtstr(C,N,''); % wrap the iterative function 
end 

function s = prtstr(C,N,prefix) 
s = cell(N^C,1); 
if C == 1 
    for ii = 1:N 
     s{ii} = [prefix, num2str(ii)]; 
    end 
else 
    BlockLen = N^(C-1); 
    for ii = 1:N 
     s((1+(ii-1)*BlockLen) : (ii*BlockLen)) = .... 
      prtstr(C-1,N,[prefix, num2str(ii)]); 
    end 
end 
end 

輸出是包含所有組合串的細胞載體。

>> s = GetCombinations(5,3) 

s = 

    '11111' 
    '11112' 
    '11113' 
    '11121' 
    '11122' 
    '11123' 
    '11131' 
    '11132' 
    '11133' 
    '11211' 
    '11212' 
    '11213' 
    '11221' 
    '11222' 
    '11223' 
    '11231' 
    '11232' 
    .... 

---

編輯：跳過重複的情況。例如，11112和11121被認爲是相同的，只列出第一個。

function s = GetCombinations(C,N) 
C = int64(C); 
N = int64(N); 
assert(C>0 && N>0, 'Invalid input') 
s = prtstr(C,N,'',1); 
s = s(~cellfun(@isempty,s)); 
end 

function s = prtstr(C,N,prefix,startN) 
s = cell(N^C,1); 
if C == 1 
    for ii = startN:N 
     s{ii} = [prefix, num2str(ii)]; 
    end 
else 
    BlockLen = N^(C-1); 
    for ii = startN:N 
     s((1+(ii-1)*BlockLen) : (ii*BlockLen)) = .... 
      prtstr(C-1,N,[prefix, num2str(ii)], ii); 
    end 
end 
end 

>> s = GetCombinations(5, 3) 

s = 

    '11111' 
    '11112' 
    '11113' 
    '11122' 
    '11123' 
    '11133' 
    '11222' 
    '11223' 
    '11233' 
    '11333' 
    '12222' 
    '12223' 
    '12233' 
    '12333' 
    '13333' 
    '22222' 
    '22223' 
    '22233' 
    '22333' 
    '23333' 
    '33333' 

---

編輯：對於大C和N，預分配單元陣列是不可行的。實際上大部分單元都是空的。哪些是空的可以預先確定，但這本身就是一個有趣的問題。然而，我只是在移動中追加單元陣列而不是預先分配它。所以慢一點，但它工作。

function s = GetCombinations(C,N) 
C = int64(C); 
N = int64(N); 
assert(C>0 && N>0, 'Invalid input') 
s = prtstr(C,N,'',1); 
s = s(~cellfun(@isempty,s)); 
end 

function s = prtstr(C,N,prefix,startN) 
s = cell(0,1); 
if C == 1 
    nt = N-startN+1; 
    t = cell(nt,1); 
    for ii = 1:nt 
     t{ii} = [prefix, num2str(ii+startN-1)]; 
    end 
    s = t; 
else 
    for ii = startN:N 
     t = prtstr(C-1,N,[prefix, num2str(ii)], ii); 
     s = [s;t]; 
    end 
end 
end 

---

編輯：記憶的版本。 請求(C,N) = (20,10)並且結果太大而無法在內存中保存。一種可能的解決方案是打印出結果而不存儲它。以下是代碼，經過測試。

function GetCombinations(C,N, fh) 
C = int64(C); 
N = int64(N); 
assert(C>0 && N>0, 'Invalid input') 
prtstr(C,N,'',1, fh); 
end 

function prtstr(C,N,prefix,startN, fh) 
if isempty(fh) % assign fh = [] if you do not want text file output 
    fh = 1; % print to command window 
end 
if C == 1 
    for ii = 1:N-startN+1 
     fprintf(fh, '%s%d\n', prefix, ii+startN-1); 
    end 
else 
    for ii = startN:N 
     prtstr(C-1,N,[prefix, num2str(ii)], ii, fh) 
    end 
end 
end 

該函數採用一個附加的輸入參數fh這是一個文件句柄。由於(20,10)具有相當多的輸出行（10m +行和200MB +），因此您可能希望將結果直接打印到文本文件中。要不然實現這一目標，

fh = fopen('testout.txt','w'); 
GetCombinations(20,10,fh) 
fclose(fh) 

，如果你真的希望將結果打印到命令窗口中，使用

GetCombinations(20,10,[])