find the unique path in a matrix

Hello! I have a matrix (shown below). The matrix is the possible indices of a vector. The width of the matrix is 18 here. The width varies for different examples. We have to choose one index from each column so that the final answer, which is a vector of length 18, should be unique. That means the final vector, if sorted, is exactly 1,2,3...,18. A sample solution is shown in the attached picture.

I do not have "graph" on my Matlab R2015a. Maybe the optimization function "fgoalattain" helps. Thank you for your help!

13  6  1  1  1  2  5  2  7  9  3  8  9  9  1  8  6  6
1  2  2  2  3  12  6  8  9  10  11  11  10  15  4  12  14  14
12  12  3  4  4  16  4  12  10  15  7  12  15  17  10  16  1  2
16  16  11  11  8  7  8  16  15  17  9  16  5  18  15  13  2  16
5  5  3  14  12  9  14  5  6  6  17  12  6  15  6  11  16  1
6  9  4  3  16  15  1  13  13  13  5  5  13  17  9  12  2  4
10  15  15  4  9  17  2  8  14  6  18  13  NaN  6  10  16  3  NaN
15  17  17  11  10  14  3  12  6  14  NaN  2  NaN  13  15  15  11  NaN
18  6  18  9  15  7  4  7  1  2  NaN  8  NaN  14  18  17  NaN  NaN
6  13  10  15  13  9  NaN  10  3  3  NaN  12  NaN  2  6  9  NaN  NaN
13  NaN  17  18  NaN  10  NaN  15  4  4  NaN  16  NaN  3  14  15  NaN  NaN
14  NaN  2  7  NaN  5  NaN  9  12  8  NaN  15  NaN  4  NaN  2  NaN  NaN
NaN  NaN  3  15  NaN  6  NaN  10  16  11  NaN  NaN  NaN  12  NaN  8  NaN  NaN
NaN  NaN  11  17  NaN  NaN  NaN  8  5  12  NaN  NaN  NaN  9  NaN  16  NaN  NaN
NaN  NaN  NaN  18  NaN  NaN  NaN  16  6  16  NaN  NaN  NaN  15  NaN  NaN  NaN  NaN
NaN  NaN  NaN  1  NaN  NaN  NaN  NaN  13  5  NaN  NaN  NaN  NaN  NaN  NaN  NaN  NaN
NaN  NaN  NaN  4  NaN  NaN  NaN  NaN  NaN  13  NaN  NaN  NaN  NaN  NaN  NaN  NaN  NaN

[John D'Errico]

So what is your question? What have you done? If nothing, then why not? Or is this a doit4me?

Note that ALL paths here will run into many millions or billions of possible paths, or more. The odds are very good that IF you did find a way to list ALL such possible paths, you would lack sufficient memory to store that list. As well, just generating that list could be hugely time consuming.

[Ali]

Thanks! I could not do anything due to out of memory problem.

[Rik]

Then this is not really a question. Try following the steps outline here. Try to figure out what exactly it is you want as a result, then try to find a way to get there. If you can't explain your question to us, we have no way of helping you.

Answer 1

[KSSV]

How about this code? Let A be your matrix, which you have given. This code is like a trial/ random, for few runs it will throw error, for the paths which we expect, it will run and show no error, this is the path which you expect.

[nx,ny] = size(A) ;
path = zeros(1,ny) ;
%%consider first column 
col = A(:,1) ;
col = col(~isnan(col)) ; % remove NaN's

path(1) = randsample(col,1) ;
for i = 2:ny
    col = A(:,i) ;
    col = col(~isnan(col)) ; % remove NaN's
    % Remove already selected number in path from this col
    col = setdiff(col,path(1:i)) ;
    %%pick one number in random from the column
    if length(col) ~=1
        path(i) = randsample(col,1) ;
    else
        path(i) = col ;
    end
end

I have run the above code for seven times, for the first six times, it throwed error and the successful result was:

path = [ 10    16     1    14    15     7     6     8    12    13    17    11     5     4
    18     9     3     2];

The above path satisfies your conditions.

[Ali]

Thanks a lot, this is a nice idea but we need all possible answers.

[KSSV]

How many possible answers there?

[Rik]

How are you going to avoid having to look through factorial(size(A,2)) possible answers (if I now understand your goal correctly)?

[Stephen23]

A recursive function could solve this without needing to look through 18! paths. Reject paths which contain a value and the number of "searches" is reduced.

[KSSV]

Check the below code: Specify the number of paths needed in N.

[nx,ny] = size(A) ;
check = 1 ;
count = 0 ;
N = 10 ;  %%Number of paths needed 
iwant = zeros(N,ny) ;
while count < N
    path = zeros(1,ny) ;
    %%consider first column
    col = A(:,1) ;
    col = col(~isnan(col)) ; % remove NaN's

      path(1) = randsample(col,1) ;

      for i = 2:ny
          col = A(:,i) ;
          col = col(~isnan(col)) ; % remove NaN's
          % Remove already selected number in path from this col
          col = setdiff(col,path(1:i)) ;
          if isempty(col)
              fail = 1 ;
              break
          end
          %%pick one number in random from the column
          if length(col) ~=1
              path(i) = randsample(col,1) ;
          else
              path(i) = col ;
          end
          fail = 0 ;
      end
      if fail ~= 1
          count = count+1 ;
          iwant(count,:) = path ;
      end    
  end

[Ali]

This was brilliant KSSV! I hope this works. Thanks a lot.

[KSSV]

Thanking is accepting the answer...