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

Untitled

By: a guest on Jun 4th, 2012  |  syntax: None  |  size: 2.09 KB  |  hits: 11  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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"
create a new version of this paste RAW Paste Data