creating sequences of unique integers drawn from an interval, which overlap with other sequences to a ceratin degree

Hello Gurus

Need your help with creating a list of integer sequences that are unique within the sequence but have certain number of common integers with other sequenes in the list.

Now we can create a list of sequences by using the combnk function in matalab which gives all the combinations of integers in a particular interval, So combnk(1:6,4) gives

     3     4     5     6
     2     4     5     6
     2     3     5     6
     2     3     4     6
     2     3     4     5
     1     4     5     6
     1     3     5     6
     1     3     4     6
     1     3     4     5
     1     2     5     6
     1     2     4     6
     1     2     4     5
     1     2     3     6
     1     2     3     5
     1     2     3     4

but I want only those sequences that differ from all other sequnces by a max of two integers for example so I want only

3 4 5 6

1 2 5 6

1 2 3 4

all other sequnces are ignored.Can you pls give me formula to calculate the number of such sequnces in a list, and also if there is a function that does this Thanks in Advance

Answer 1

[Geoff Hayes]

You could use the intersect function (type help intersect in the Command Window for details) to determine how many elements are common in any two rows of the matrix A, and if that number is greater than two, then you know to exclude that second row. If you were to start with the first row, you could then compare all others to it and remove those that have more than two elements in common:

 % suppose A is your matrix from above
 m            = size(A,1);
 rowsToRemove = []; % lis
 for i=2:m      % start with second row and iterate over all remaining rows of A
     if length(intersect(A(1,:),A(i,:)))>2
         % record this i as a row to remove
         rowsToRemove = [rowsToRemove ; i];
     end
  end

% remove all rows from A that have more than 2 elements in common with row 1
A(rowsToRemove,:) = [];

A is now (perhaps) reduced in size, so repeat the above starting at the second row. Keep iterating in this manner until there you have reached the last row of the (reduced) A. And you're done.

[A K]

Thanks Geoff.

I was doing something along those lines. As you suggest the intersect is probably more efficient than comparing each number in a row.

Also I wonder if you could help me with a formula that calculates the number of such sequences, as I need to verify the result.

I find the number of such sequences I get is rather small in number. So if I use combnk(1:30,10) I get around 30 million unique sequences, but only around 55 of them have less than or equal to 4 numbers in common with all other sequences.

I would like to verify this result with an anlytical formula.

Thanks

[Geoff Hayes]

Coming up with an analytical formula would be interesting. Perhaps summing up all possibilities of there being no two elements in common, exactly one element in common, and exactly two elements in common. That may be doable.