find corresponding elements in a vector

Hello everyone! Let's assume we have the vectors U and V:

U=[6 6 18 18 3 19 12 18 24 24 10 22 11 27 28 18 12 12];

V=[5 7 10 10 21 2 21 10 23 7 1 13 2 19 10 1 13 21];

The length of the vectors usually ranges from 9 to 20. We are trying to correspond each element of U to one element in V which satisfies certain conditions. For example, the right answer satisfies either U(j) = V(i) + abs(i-j) or U(j) = V(i) - abs(i-j)

The problem is using perms for length>9 goes to memory error. Any help is appreciated. I am running on a 32Bit. Thanks!

[KSSV]

Give the complete code, which lead to error..

[Ali]

perms(1:10) Out of memory. Type HELP MEMORY for your options.

[Walter Roberson]

"We are trying to correspond each element of U to one element in V which satisfies certain conditions."

U(2) = V(1) + abs(1-2) %6 = 5 + abs(-1)

U(2) = V(6) + abs(2-6) %6 = 2 + abs(-4)

So, are we to choose the first of the solutions, or the last, or any one which is convenient ?

[KSSV]

perms(1:10) is giving you a matrix of size 3628800*10, this number is huge for your memory...so error popped. Is it necessary to generate such huge matrix?

[Ali]

Thanks Walter! The point is the conditions are satisfied only for one unique set. Maybe U(2) can be linked to V(1) and V(6) but U(i) can only be linked to V(1) which forces the U(2) to connect to V(6) only.

Answer 1

[Roger Stafford]

A general approach:

If the number of elements is n for both U and V, you can easily construct an n-by-n logical matrix, L, in which an element at the i-th row and j-th column will be true if the given condition holds between U(i) and V(j), and false otherwise.

The task then is to find a subset S of n elements of L which are all true and such that each row has exactly one element of S and similarly each column has exactly one element of S. Such a set amounts to a permutation of the n possible indices 1:n. In general the number of such possible subsets, S, will be very much less than the number, factorial n. A code consisting of n nested for-loops could easily be made to do the searching, but in order to produce code that accepts n as a variable parameter, probably the best method would be a recursive function that simulates such nested loops. In all of this there should be no problem with excessive memory storage.

[Stephen23]

U = [6,6,18,18,3,19,12,18,24,24,10,22,11,27,28,18,12,12];
V = [5,7,10,10,21,2,21,10,23,7,1,13,2,19,10,1,13,21];

Vi = V(:);
Uj = U(:).';
[I,J] = ndgrid(1:numel(Vi),1:numel(Uj));
Dm = bsxfun(@minus,Uj,Vi);
X = bsxfun(@eq,abs(Dm),abs(I-J))

giving

X =  
  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  1  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0
  0  1  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0
  0  0  0  1  0  0  0  0  0  1  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  1  0  0  0  0  0  1  0  1  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  1  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1
  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

However the statement that "the conditions are satisfied only for one unique set" is incorrect as many rows and columns do not contain any ones at all, as Walter Roberson has already pointed out.

[Ali]

Thanks a lot. If you can send me an example link for recursive function, I would appreciate.

Answer 2

[Walter Roberson]

In R2016b or later, you can express the search as

matches = ~(U.' -V + abs((1:18) .' - (1:18))) | ~(U.' -V - abs((1:18) .' - (1:18)));

This will give you a binary array of matches. For example the first row is

     0   1   0   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0

reflecting that U(1) and V(2) are in the right relationship and U(1) and V(14) are in the right relationship.

You posted that "The point is the conditions are satisfied only for one unique set." but with those U and V values, there are no matches for U([3 11 12 13 14 15]) or for V([3 4 10 11 13 16 18])

[Ali]

I put the manual solution in Excel above. Thanks!

[Walter Roberson]

Your variable POOL does not appear to occur in your original question in any form.

[Ali]

Sorry, I did not want to put you in trouble.