Сортировать массив точно так же, как пример строки

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, поэтому я подумал о том, чтобы, возможно, использовать подход с использованием базы данных и сохранить элементы в базе данных, а затем использовать некоторые ключи для восстановления оригинальной строки ... но, возможно, лучше просто выполнить какой-то трюк с сортировкой. Результат не обязательно должен быть массивом, может быть чем угодно ..

Спасибо за любой вклад.

P.S. включая тег 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