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

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.

[dpb]

"So after '1' 2 & 13 are only possible..."

Well, that means if you start with first row being [1 2 ...], there are still perms(3:24) combinations for only that first row or

>> factorial(22)
ans =
   1.1240e+21
>> 

combinations for the first row alone.

Physically impossible to do what you ask...you're going to have to find another way.

[AMAL VASU]

The condition is not only for the first number but also for all the numbers except the last one.

[Torsten]

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]

@Torsten I see [2, 13] as next of 1 and nowhere 1.

For your question, see the discussion comments under my answer.

Answer 1

[Bruno Luong]

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

[AMAL VASU]

First of all thank you for your answer. The starting number can be anyone from 1 to 24. I think it is not clear in my question.

[Bruno Luong]

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

[AMAL VASU]

Thank you so much for the help!!!

Answer 2

[Steven Lord]

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?

[AMAL VASU]

Actually I would like to find all possible fluid flow paths of a heat exchanger having 12 tubes in vertical direction and there are two such rows of tubes which makes total of 24 tubes. The condition is that only nearby tubes are connected.

Tubes are numbered from top to bottom in a row.

1
    13
2
    14
3
    15
4
    16
.....
.....
......
    12
24

2 to 3 ,2 to 13 , 2 to 14 possible ,but 2 to 4 , 2 to 15 not possible.

[Steven Lord]

Actually I would like to find all possible fluid flow paths of a heat exchanger having 12 tubes in vertical direction

Okay, let's say you were able to find all those flow paths. Then what? Do you want to do something like determine the maximum amount of fluid that can flow through the system at one time?

[AMAL VASU]

No, I need to find the optimal flow path. The objective function can be anything like maximum heat transfer or minimum prtessure drop. So I need to do simulation for all possible paths to find the best one.

[Bruno Luong]

"No, I need to find the optimal flow path. "

That could be solved by "shortest path algorithm" if you cost function is the sum of cost function apply for a simple edge between two nodes.

[Torsten]

That could be solved by "shortest path algorithm" if you cost function is the sum of cost function apply for a simple edge between two nodes.

... under the constraint that all nodes are visited exactly once - at least from the OP's previous problem formulation. So a little harder.

[Bruno Luong]

Ops, I wanted to said TSP not shortest path algorithm.

[AMAL VASU]

Thank you for your response

[dpb]

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.