MATLAB: Find corresponding elements in a vector

matchpermsvector

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!

Best Answer

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.
Related Question