Question: I want to find the similarity of two sequences in Ruby based solely on the quantity of shared values. The sequential position of the values should be irrelevant. What should also be irrelevant is whether one sequence has any values that the other sequence does not have. Levenshtein distance was suggested to me, but it computes the number of edits required to make the sequences *identical*. Here's a simple example of where the flaw is there:

```
[1,2,3,4,5]
[2,3,4,5,6,7,8,9]
#Lev distance is 5

[1,2,3,4,5]
[6,7,8,9,10]
#Lev distance is 5

```

In a perfect world the first set would have much greater similarity than the second set. The crude, obvious solution is to use nested loops to check each value of the first sequence against each value of the second. Is there a more efficient way?

Answer: 
You can do an intersection for a pair of arrays using an `&` like this:

```
a = [1,2,3,4,5]
b = [2,3,4,5,6,7,8,9]

common = a & b   # =>  [2, 3, 4, 5]
common.size      # =>  4

```

Is this what you are looking for?
If the sequences are sorted (or you sort them), all you have to do is walk down both lists, incrementing the similarity counter and popping off both values if they match. If they don't match, you pop off the smaller value, and continue until one list is empty. The complexity of this is O(n log n) for the sorting plus O(n) for the walk, where n is the sum of the lengths of the two lists.

You could also loop through each list, counting the incidence of each number (so you end up with a list of the counts of each value). Then you could compare these quantities, incrementing the similarity counter by the lesser count for each value.