How can I get permutations of a vector satisfying the given condition?
3 次查看(过去 30 天)
显示 更早的评论
I need to get all permutations of an array (A=[1:24] ) satisf[y]ing given conditions.The very next number after the given number can be only as per the condition mentioned. For example next number after '1' can be the non zero elements in the first row of the given matrix B. So each row represents the possible 'next numbers' of the number representing the row.
So after '1' 2 & 13 are only possible
after '2' (second row) 1,3,14&13 are possible.
after 23 (23rd row) 22,24,11&12 are possible .
B= [0 2 0 13 0 0;
1 3 0 14 0 13;
2 4 0 15 0 14;
3 5 0 16 0 15;
4 6 0 17 0 16;
5 7 0 18 0 17;
6 8 0 19 0 18;
7 9 0 20 0 19;
8 10 0 21 0 20;
9 11 0 22 0 21;
10 12 0 23 0 22;
11 0 0 24 0 23;
0 14 1 0 2 0;
13 15 2 0 3 0;
14 16 3 0 4 0;
15 17 4 0 5 0;
16 18 5 0 6 0;
17 19 6 0 7 0;
18 20 7 0 8 0;
19 21 8 0 9 0;
20 22 9 0 10 0;
21 23 10 0 11 0;
22 24 11 0 12 0;
23 0 12 0 0 0];
I am not able to apply this condtion after finding all permutation of vector A as 'perms' function can not generate all possible permutation due to storge and time limitations.
4 个评论
Torsten
2022-8-1
Should all paths start with "1" or with one of the nodes "2" or "13" ?
If all paths start with "1", why is "1" still listed in the matrix as "next node" option ?
Bruno Luong
2022-8-1
编辑:Bruno Luong
2022-8-1
@Torsten I see [2, 13] as next of 1 and nowhere 1.
For your question, see the discussion comments under my answer.
采纳的回答
Bruno Luong
2022-8-1
编辑:Bruno Luong
2022-8-1
There are 9918 permutations according to this code
B= [0 2 0 13 0 0;
1 3 0 14 0 13;
2 4 0 15 0 14;
3 5 0 16 0 15;
4 6 0 17 0 16;
5 7 0 18 0 17;
6 8 0 19 0 18;
7 9 0 20 0 19;
8 10 0 21 0 20;
9 11 0 22 0 21;
10 12 0 23 0 22;
11 0 0 24 0 23;
0 14 1 0 2 0;
13 15 2 0 3 0;
14 16 3 0 4 0;
15 17 4 0 5 0;
16 18 5 0 6 0;
17 19 6 0 7 0;
18 20 7 0 8 0;
19 21 8 0 9 0;
20 22 9 0 10 0;
21 23 10 0 11 0;
22 24 11 0 12 0;
23 0 12 0 0 0];
P = AllHpath(B);
fprintf('there are %d permutations\n', size(P,1))
% Display 10 solutions
P([1:5 end-4:end],:)
function P = AllHpath(B)
P = Hpath_helper(B, 1, size(B,1));
end
function P = Hpath_helper(B, i, n)
if n == 1
P = i;
else
Bi = B(i,:);
next = Bi(Bi>0);
P = zeros(0,n);
if ~isempty(next)
B(B==i) = 0;
P = [];
for k = next
Pk = Hpath_helper(B, k, n-1);
P = [P; [repmat(i,size(Pk,1),1), Pk]]; %#ok
end
end
end
end
3 个评论
Bruno Luong
2022-8-1
编辑:Bruno Luong
2022-8-1
Then change (loop on) the second argument "1" in this command, which is the starting number
P = Hpath_helper(B, 1, size(B,1))
the function becomes
function P = AllHpath(B)
n = size(B,1);
CP = arrayfun(@(start) Hpath_helper(B, start, n), 1:n, 'unif', 0);
P = cat(1,CP{:});
end
there are 48860 permutations
更多回答(1 个)
Steven Lord
2022-7-31
My first thought would be to construct a digraph from your data then try to find Hamiltonian paths in that digraph. Or there may be a way to use the digraph to solve your underlying problem without having to determine all permutations of its nodes. What is that underlying problem you're trying to solve?
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Robust Control Toolbox 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!