Return 可能重复的数组元素的所有唯一排列

Question

假设我有一个长度为 N 的数组，其中包含 M 个不同的对象 (M < N)，因此其中一些对象会重复 N_i ... N_M 次。我想找到此类数组元素的所有可能 unique 配置（如排列），而无需事先计算整个排列列表（时间和内存限制）。

当然，天真的解决方案是使用 perms 生成所有可能的排列，然后 select 唯一的排列：

A = [1, 1, 2];

all_perms = perms(A)
    % all_perms =

    % 2     1     1
    % 2     1     1
    % 1     2     1
    % 1     1     2
    % 1     2     1
    % 1     1     2

unique_perms = unique(all_perms, 'rows')
    % unique_perms =

    % 1     1     2
    % 1     2     1
    % 2     1     1

但这将生成所有 N! 排列，而不仅仅是 N! / (N_1! * N_2! * ... * N_M!)。对于 N = 3，这对内存消耗和计时都没有太大影响，但随着 N 的增加和唯一元素数量的减少，差异可能会很大。所以：

是否有一种（希望是内置的）方法来列出包含非不同对象的数组的所有唯一排列，而无需中间保留 all 排列？

Answer 1

以下是 Bruno Luong 在 2014 年针对此问题建议的代码：

function p = uperm(a)
[u, ~, J] = unique(a);
p = u(up(J, length(a)));
end % uperm

function p = up(J, n)
ktab = histc(J,1:max(J));
l = n;
p = zeros(1, n);
s = 1;
for i=1:length(ktab)
    k = ktab(i);
    c = nchoosek(1:l, k);
    m = size(c,1);
    [t, ~] = find(~p.');
    t = reshape(t, [], s);
    c = t(c,:)';
    s = s*m;
    r = repmat((1:s)',[1 k]);
    q = accumarray([r(:) c(:)], i, [s n]);
    p = repmat(p, [m 1]) + q;
    l = l - k;
end
end

可以通过将 nchoosek 替换为 Jan Simon's functions.

之一来进一步改进上述内容

Return 可能重复的数组元素的所有唯一排列

Return all unique permutations of possibly-repeating array elements

arrays

matlab

permutation

combinatorics

built-in