1

Possible Duplicate:
Reverse the ordering of words in a string

I know there are methods that python already provides for this, but I'm trying to understand the basics of how those methods work when you only have the list data structure to work with. If I have a string hello world and I want to make a new string world hello, how would I think about this?

And then, if I can do it with a new list, how would I avoid making a new list and do it in place?

Community
  • 1
  • 1
locoboy
  • 38,002
  • 70
  • 184
  • 260

4 Answers4

14

Split the string, make a reverse iterator then join the parts back.

' '.join(reversed(my_string.split()))

If you are concerned with multiple spaces, change split() to split(' ')

As requested, I'm posting an implementation of split (by GvR himself from the oldest downloadable version of CPython's source code: Link)

def split(s,whitespace=' \n\t'):
   res = []
   i, n = 0, len(s)
   while i < n:
       while i < n and s[i] in whitespace:
           i = i+1
       if i == n:
           break
       j = i
       while j < n and s[j] not in whitespace:
           j = j+1
       res.append(s[i:j])
       i = j
   return res

I think now there are more pythonic ways of doing that (maybe groupby) and the original source had a bug (if i = n:, corrrected to ==)

JBernardo
  • 32,262
  • 10
  • 90
  • 115
  • How does reversed work if I had to program it out? – locoboy Oct 08 '11 at 10:43
  • @cfarm reverse returns an iterator. You would have to loop the container from it's size to zero, [`yield`](http://stackoverflow.com/questions/231767/the-python-yield-keyword-explained/231855#231855)ing the values – JBernardo Oct 08 '11 at 13:03
  • how does split work? can you write out the code for both split and reversed? – locoboy Oct 08 '11 at 13:48
  • split create a list by iterating a string and finding a separator. You don't want to code them yourself (although it would be pretty simple) because would be too slow and re-inventing the wheel. – JBernardo Oct 08 '11 at 16:30
7

Original Answer

from array import array

def reverse_array(letters, first=0, last=None):
    "reverses the letters in an array in-place"
    if last is None:
        last = len(letters)
    last -= 1
    while first < last:
        letters[first], letters[last] = letters[last], letters[first]
        first += 1
        last -= 1

def reverse_words(string):
    "reverses the words in a string using an array"
    words = array('c', string)
    reverse_array(words, first=0, last=len(words))
    first = last = 0
    while first < len(words) and last < len(words):
        if words[last] != ' ':
            last += 1
            continue
        reverse_array(words, first, last)
        last += 1
        first = last
    if first < last:
        reverse_array(words, first, last=len(words))
    return words.tostring()

Answer using list to match updated question

def reverse_list(letters, first=0, last=None):
    "reverses the elements of a list in-place"
    if last is None:
        last = len(letters)
    last -= 1
    while first < last:
        letters[first], letters[last] = letters[last], letters[first]
        first += 1
        last -= 1

def reverse_words(string):
    """reverses the words in a string using a list, with each character
    as a list element"""
    characters = list(string)
    reverse_list(characters)
    first = last = 0
    while first < len(characters) and last < len(characters):
        if characters[last] != ' ':
            last += 1
            continue
        reverse_list(characters, first, last)
        last += 1
        first = last
    if first < last:
        reverse_list(characters, first, last=len(characters))
    return ''.join(characters)

Besides renaming, the only change of interest is the last line.

Ethan Furman
  • 63,992
  • 20
  • 159
  • 237
  • what does `words = array('c', string)` do? – locoboy Oct 08 '11 at 14:02
  • @cfarm54: it creates an `array` object that contains whatever is in `string`, of type character. Check out the [docs](http://docs.python.org/library/array.html?#module-array). – Ethan Furman Oct 08 '11 at 14:07
  • so right now this doesn't quite work for me. if `string = "hello world"`, then `len(words)` is 11. – locoboy Oct 08 '11 at 14:12
  • @cfarm54: What were you expecting? if `string = "hello world"` you get back `"world hello"`, which is what you asked for. – Ethan Furman Oct 08 '11 at 15:13
  • @cfarm54: `len(words)` is eleven because `words` is a string of eleven characters -- you did say you wanted a string back. Oh, updated my answer to use a list instead of an array. – Ethan Furman Oct 08 '11 at 23:53
5

You have a string:

str = "A long string to test this algorithm"

Split the string (at word boundary -- no arguments to split):

splitted = str.split()

Reverse the array obtained -- either using ranges or a function

reversed = splitted[::-1]

Concatenate all words with spaces in between -- also known as joining.

result = " ".join(reversed)

Now, you don't need so many temps, combining them into one line gives:

result = " ".join(str.split()[::-1])
Mihai Maruseac
  • 20,967
  • 7
  • 57
  • 109
  • I don't understand why this is downvoted. It walks through the steps of an existing answer that the OP wanted clarified, and arrives at the same, correct result. – Karl Knechtel Oct 08 '11 at 06:13
  • 1
    @KarlKnechtel: They are all decent answers, except for not answering the question as asked -- none of them use arrays. – Ethan Furman Oct 08 '11 at 06:34
1
str = "hello world"
" ".join(str.split()[::-1])
  • Could you explain the logic here? Also, as indicated in the question, I'm trying to understand the basics of doing this with just arrays. Meaning start with `str = 'hello world'` then create an array and reverse the words. – locoboy Oct 08 '11 at 05:29
  • The string is split into words with a built-in function. Using the `[::-1]` slice reverses the split-up list, in the way explained in the other question you asked and the linked duplicate. The reversed list of words is then joined back up together with spaces. Please note the word 'list'. In Python, an array is something quite different. – Karl Knechtel Oct 08 '11 at 06:12