Sort an array exactly like example string

Question

What would be the optimal solution for the following problem?

I have

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

I also have

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

I need to sort the array, so that elements are in the same order as in string. The elements are sometimes grouped together, but always in the same way as they are in string (i.e. there can be no 'is This' element in the array, only 'This is')..

All this is happening within the Rails application, so I was thinking of maybe taking the database approach and saving elements in database and then using some keys to reconstruct the original_string.. but maybe just doing some .sort trick is better.. The result does not necessarily have to be an array, can be anything..

Thanks for any input.

P.S. including an nlp tag, because this is a result of some nlp exercise.

Amadan · Accepted Answer · 2011-12-29 01:06:37Z

7

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

The result is a new array, sorted by the position of the substring in the original string.

If you want to sort in-place (by changing the original array), you can use the sort_by! method instead.

Obviously, it's too stupid to detect doubles (i.e. "I am what I am", ["I am", "I am", "what"] will not be sorted as one hopes).

EDIT Making it not quite so stupid is not quite so trivial:

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

edited Dec 29, 2011 at 1:06

answered Dec 28, 2011 at 21:26

Amadan

200k23 gold badges252 silver badges321 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

tokland Over a year ago

Won't String#index find the first occurrence anywhere in the string?(without considering if it's a full word)

Amadan Over a year ago

They will. I just reread the question, and them being words was not specified. If they need to be words, you can deal with it by regexp-quoting the substring, surrounding with word-boundary matchers, then compare the length of the pre-match.

Stpn Over a year ago

can you give an example? Sorry for this postscriptum, but the original_string can be rather complex in my case..

Amadan Over a year ago

Example for what? Matching only full words?

Stpn Over a year ago

For the case where the words will repeat for example original_string = 'This string has information about string theory' and example_array = ['This','string', 'information about', 'has', 'theory', 'string'] Thanks )

Collectives™ on Stack Overflow

Sort an array exactly like example string

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related