Don't like ads? PRO users don't see any ads ;-)

# Untitled

By: a guest on Jun 4th, 2012  |  syntax: None  |  size: 2.09 KB  |  hits: 11  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. Subsequence search
2. 1, 2, 3, 4, 5, 6
3. 1, 2, 2, 3, 3, 3
4.
5. 6, 5, 4, 3, 2, 1
6. 123, 4, 5, 6, 7
7.
8. Hash<int, List<int>> index
9.
10. line_number = 1
11. foreach(line in filereader)
12. {
13.     line_number += 1
14.     foreach(parsed_number in line)
15.         index[parsed_number].append(line)
16. }
17.
18. // prefilled hash linking number searched for to a list of line numbers
19. // the lines should be in ascending order
20. Hash<int, List<int>> index
21.
22. // The subsequence we're looking for
23. List<int> subsequence = {1, 2, 3}
24. int len = subsequence.length()
25.
26. // Take all the lists from the index that match the numbers we're looking for
27. List<List<int>> lines = index[number] for number in subsequence
28.
29. // holder for our current search row
30. // has the current lowest line number each element occurs on
31. int[] search = new int[len]
32. for(i = 0; i < len; i++)
33.     search[i] = lines[i].pop()
34.
35. while(true)
36. {
37.     // minimum line number, substring position and whether they're equal
38.     min, pos, eq = search[0], 0, true
39.
40.     // find the lowest line number and whether they all match
41.     for(i = 0; i < len; i++)
42.     {
43.         if(search[i] < min)
44.             min, p, eq = search[i], i, false
45.         else if (search[i] > min)
46.             eq = false
47.     }
48.
49.     // if they do all match every one of the numbers occurs on that row
50.     if(eq)
51.     {
52.         yield min; // line has all the elements
53.
54.         foreach(list in lines)
55.             if(list.empty())  // one of the numbers isn't in any more lines
56.                  return
57.
58.         // update the search to the next lowest line number for every substring element
59.         for(i = 0; i < len; i++)
60.             search[i] = lines[i].pop()
61.     }
62.     else
63.     {
64.         // the lowest line number for each element is not the same, so discard the lowest one
65.         if(lines[position].empty()) // there are no more lines for the element we'd be updating
66.             return
67.
68.         search[position] = lines[position].pop();
69.     }
70. }
71.
72. search = [1 2 3]
73. for sequence in sequences:
74.   sidx = 0
75.   for item in sequence:
76.     if item==search[sidx]:
77.        sidx++
78.        if sidx>=len(search): break
79.   if sidx>len(search):
80.     print sequence + "matches"