生成所有组合以扩展到大列

Question

我有 C 列，我想在其中填充 N 元素的所有组合 (C>N)。我如何在 Matlab 中完成？
例子：C=5，N=3；然后将 N 从 1 到 N 即 1 到 3 的所有组合填充到 C=5 列中。我试过 NchooseK 但无法实现。预期输出如下所示：

输出：11111， 11112, 11122, 11222, ....., 22222, 22223, 22233, ....., 33333, ..... 12312, 12313, 12323, ...等等...
以这种方式，1 到 N 的所有组合最多填充 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)

否则，如果你真的想把结果打印到命令window，使用

GetCombinations(20,10,[])

生成所有组合以扩展到大列

generate all combinations to extend to large columns

matlab

combinations

element