How to generate all possible permutations without using the function perms/randperm?
显示 更早的评论
Hello
I am trying to generate all possible permutations (permMat) of a matrix, say A = [1:4], without using the function perms as that is not allowed, but I am stuck.
So far I have came up with
while size(permMat,1) ~= factorial(4)
%to find a random permutation of A
while length(r3)~= 4 %where r3 is a random permutation of A
x=randi([1,C]);
if sum(r3==x)==0
r3=[r3 x];
end
end
permMat = [permMat;r3];
permMat = unique(permMat,'rows');
end
However, I realised that using this above method to find a random permutation will only result in the same permutation in the loop. Is there anyway to generate a always-changing random permutation in the loop? Or is there a better way to generate all possible permutations?
Thanks!
采纳的回答
John D'Errico
2016-10-20
Using random permutations to try to generate all possible permutations is simply insane. Sorry, but you will never be happy with that approach. Even for small sets of elements this will be terribly inefficient.
You can simply generate all possible permutations using a recursive scheme, given a vector v of elements, where v is not too long. For a vector of length n, there will be factorial(n) permutations, so if n is greater than about 10 or so, ANY scheme will take some effort.
function P = myperms(v)
% simple recursive scheme to generate all permutations of a vector v.
n = numel(v);
if n <= 1
P = v;
else
P = zeros(factorial(n),n);
f = factorial(n-1);
L = 1:f;
for ii = n:-1:1
P(L,1) = v(ii);
P(L,2:n) = myperms(v(setdiff(1:n,ii)));
L = L + f;
end
end
As you can see, it works.
myperms([2 3 5])
ans =
5 3 2
5 2 3
3 5 2
3 2 5
2 5 3
2 3 5
perms([2 3 5])
ans =
5 3 2
5 2 3
3 5 2
3 2 5
2 5 3
2 3 5
Same set of permutations, even in the same order.
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
