How can I get permutations of a vector satisfying the given condition?

7 views (last 30 days)
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 Comments
Bruno Luong
Bruno Luong on 1 Aug 2022
Edited: Bruno Luong on 1 Aug 2022
@Torsten I see [2, 13] as next of 1 and nowhere 1.
For your question, see the discussion comments under my answer.

Sign in to comment.

Accepted Answer

Bruno Luong
Bruno Luong on 1 Aug 2022
Edited: Bruno Luong on 1 Aug 2022
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))
there are 9918 permutations
% Display 10 solutions
P([1:5 end-4:end],:)
ans = 10×24
1 2 3 4 5 6 7 8 9 10 11 12 24 23 22 21 20 19 18 17 16 15 14 13 1 2 13 14 15 16 17 18 19 20 21 22 23 24 12 11 10 9 8 7 6 5 4 3 1 2 13 14 15 3 4 5 6 7 8 9 10 11 12 24 23 22 21 20 19 18 17 16 1 2 13 14 15 3 4 5 16 17 18 19 20 21 22 23 24 12 11 10 9 8 7 6 1 2 13 14 15 3 4 5 16 17 18 6 7 8 9 10 11 12 24 23 22 21 20 19 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 23 11 12 24 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 12 24 23 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 12 23 24 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 23 24 12 1 13 2 14 3 15 4 16 5 17 6 18 7 19 8 20 9 21 10 22 11 23 12 24
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 Comments

Sign in to comment.

More Answers (1)

Steven Lord
Steven Lord on 31 Jul 2022
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?
  8 Comments
dpb
dpb on 1 Aug 2022
Edited: dpb on 3 Aug 2022
Given the problem and the geometry, you can simply solve for one set of connected tubes and by symmetry know the answer for the rest...
.....
13
2
14
3
.....
You could, if wanted, also do the ends as second geometry.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!