生成具有受控输出的集合的排列？

Question

有没有简单的方法来获得集合的前 x 个排列？

例如，包含 5 个字符 {a,b,c,d,e} 的集合将有

5*5*5*5*5= 3125个排列输出

（允许重复，例如 {a,a,a,a,a}）

但我只想获得例如前 100 个值

Answer 1

您可以使用 P = perms(S) 来获取集合 S 的所有排列，然后如果您想要 100，您可以使用 P(1:100,:)。

对于随机你可以使用 P(randperm(size(P,1),100),:).

如果您知道需要更具体的排列，那么您可以使用带有 order 参数的 permute - http://uk.mathworks.com/help/matlab/ref/permute.html

Answer 2

一种按字典顺序一次生成所有 'permutations' 的方法，而不必将它们全部存储在内存中：

function permute_chars(alphabet, nword, nmax)

if nargin < 3  % default to displaying all, this can be a huge number!
    nmax = nchar^nword;
end

nchar = length(alphabet);
ind = zeros(1, nword);
i = 0;

while i < nmax
    % just printing the permutaions, edit according to your needs
    disp(cell2mat(alphabet(ind + 1))); 

    % calculate next indices, classic elementary school addition with carry
    ind(end) = ind(end) + 1;
    for j = nword:-1:2
        if ind(j) == nchar 
            ind(j) = 0;  % wrap around
            ind(j-1) = ind(j-1) + 1;  % carry
        end
    end     
    i = i + 1;
end

我确实忘记了一些晦涩的函数，这些函数可以用更少的行来实现它，但是这样写很清楚它是如何工作的。快速测试：

>> alphabet = {'a', 'b', 'c', 'd', 'e'};
>> permute_chars(alphabet, 1)
a
b
c
d
e
>> permute_chars(alphabet, 2)
aa
ab
ac
ad
ae
ba
[... snip ...]
ed
ee

仅打印有限数量的排列：

>> permute_chars(alphabet, 5, 8)
aaaaa
aaaab
aaaac
aaaad
aaaae
aaaba
aaabb
aaabc

Answer 3

到 select 100 个来自数字 1:n 的随机唯一样本，允许重复（有放回的抽样），您可以使用 randi 或类似的方法来创建更多的列表比 100 x n 个随机样本，unique 它们删除重复项，然后取前 100 个。

例如，使用randi:

% from numbers 1:n, create 200 by n random matrix
sample_list = randi(n,[200, n]);
% remove duplicates
sample_list = unique(sample_list,'rows'); 
% you should probably error check here
% presuming there's >100 options left, take 100 of them
sample_list = sample_list(1:100,:);

sample_list 将是一个数字矩阵，但如果需要，您可以轻松地将其用作其他事物的索引：

my_set = {'a','b','c','d','e'}; % 1 x 5 cell
my_permutes = my_set(sample_list); % 100 x 5 cell

这避免了必须计算每个可能的选项，这对于更大的 n 会成为问题。

Answer 4

为了更灵活地获得排列的范围，您可以使用一个函数，该函数在给定排列的情况下生成系列中的下一个排列。在这个实现中，我选择让排列回到第一个，即使输入排列超出范围。

function newperm = nextPerm(oldperm, base)
   if any(oldperm >= base)
      newperm = zeros(1,numel(oldperm));
      return
   end
   idx = numel(oldperm);
   newperm = oldperm;
   while idx > 0
      newperm(idx) = newperm(idx) + 1;
      if newperm(idx) < base
         return;
      end
      newperm(idx) = 0;
      idx = idx - 1;
   end
end

排列元素从 0 开始（因此最大元素以 1 为底）。

p = [4 4 4 4 4]
nextPerm(p, 5)
ans =

   0   0   0   0   0

p = [0 0 0 0 0]
nextPerm(p, 5)
ans =

   0   0   0   0   1

p = [3 4 1 0 2]
nextPerm(p, 5)
ans =

   3   4   1   0   3

p = [3 4 5 0 2] %// invalid value '5'
nextPerm(p, 5)
ans =

   0   0   0   0   0

要获得一个范围，只需将其输入一个循环即可：

myPerms = zeros(5);
myPerms(1,:) = [3 1 2 0 4];
for k = 2:5
   myPerms(k,:) = nextPerm(myPerms(k-1,:), size(myPerms,1));
end

myPerms =

   3   1   2   0   4
   3   1   2   1   0
   3   1   2   1   1
   3   1   2   1   2
   3   1   2   1   3

要将排列映射到您的字母表，只需将向量加 1 并将其用作索引：

alphabet = ['a', 'b', 'c', 'd', 'e'];
word = alphabet(myPerms(1,:)+1)

word = dbcae

生成具有受控输出的集合的排列？

Generating permutations of a set with controlled output?

matlab

permutation