对数组进行排序就像示例字符串一样

Question

以下问题的最佳解决方案是什么？

我有

original_string = "This is a string that I am trying to sort"

我也有

array_to_sort = ['sort', 'string', 'This is', 'I', 'trying to', 'am', 'a'] 

我需要对数组进行排序,以便元素的顺序与字符串中的顺序相同.这些元素有时会组合在一起,但总是与它们在字符串中的方式相同(即数组中没有'is This'元素,只有'This is').

所有这一切都发生在Rails应用程序中,所以我想可能采用数据库方法并在数据库中保存元素,然后使用一些键来重建original_string ..但也许只是做一些.sort技巧更好..结果确实不一定是一个数组,可以是任何东西..

感谢您的任何意见.

PS包括一个nlp标签,因为这是一些nlp练习的结果.

Answer 1

array_to_sort.sort_by { |substr| original_string.index(substr) }

结果是一个新数组,按原始字符串中子字符串的位置排序.

如果要在原地排序(通过更改原始数组),则可以使用该sort_by!方法.

显然,检测双打是太愚蠢(即"I am what I am", ["I am", "I am", "what"]不会按照人们的希望排序).

编辑使它不那么愚蠢并不是那么微不足道:

def get_all_positions(str, substr)                                                                                                                                                                                           
  pattern = Regexp.new('\b' + Regexp::escape(substr) + '\b')
  result = []
  pos = -1
  while match = pattern.match(str, pos + 1)
    pos = match.offset(0)[0] + 1
    result << pos
  end
  result
end

def sort_array_according_to_string(arr, str, i=0, positions=nil)
  positions ||= Hash.new
  if i < arr.count
    current = arr[i]
    current_positions = get_all_positions(str, current)
    result = []
    current_positions.each do |pos|
      if !positions[pos]
        positions[pos] = [pos, i, current]
        result += sort_array_according_to_string(arr, str, i + 1, positions)
        positions.delete(pos)
      end
    end
  else
    sorted = positions
      .values
      .sort_by { |position, i| position }
      .map { |position, i| arr[i] }
    result = [sorted]
  end
  if i == 0
    result.uniq!
  end
  result
end

original_string = 'this is what this is not'
example_array = ['this', 'is', 'is not', 'what', 'this']
solution = sort_array_according_to_string(example_array, original_string)
puts solution.inspect