5
\$\begingroup\$

Q1. Define a function reverse_list that takes a list as an argument and returns None, but reverses the elements in the list as a side effect. Do not use any built-in list methods (especially not reverse), but assignment statements are fine.

Below is the iterative solution:

def reverse_list_iter(s):
    """Reverse the contents of the list s and return None.

    >>> digits = [6, 2, 9, 5, 1, 4, 1, 3]
    >>> reverse_list_iter(digits)
    >>> digits
    [3, 1, 4, 1, 5, 9, 2, 6]
    >>> d = digits
    >>> reverse_list_iter(d)
    >>> digits
    [6, 2, 9, 5, 1, 4, 1, 3]
    """
    median = len(s)//2
    length = len(s)
    for index in range(median):
        temp = s[index]
        s[index] = s[(length - 1) - index]
        s[(length - 1) - index] = temp

Below is the recursive solution:

def reverse_list_recur(s):
    """Reverse the contents of the list s and return None.

    >>> digits = [6, 2, 9, 5, 1, 4, 1, 3]
    >>> reverse_list_recur(digits)
    >>> digits
    [3, 1, 4, 1, 5, 9, 2, 6]
    >>> d = digits
    >>> reverse_list_recur(d)
    >>> digits
    [6, 2, 9, 5, 1, 4, 1, 3]
    """
    median = len(s)//2
    length = len(s)
    def reverse(index):
        if index == median:
            return
        else:
            temp = s[index]
            s[index] = s[(length - 1) - index]
            s[(length - 1) - index] = temp
            reverse(index + 1)
    reverse(0)

How can I improve the solution?

\$\endgroup\$
0
6
\$\begingroup\$

In general, Python's tuple assignment and unpacking allows you to rewrite:

temp = foo
foo = bar
bar = temp

as:

foo, bar = bar, foo

which saves you two lines in both versions! This gets you to:

s[index], s[(length - 1) - index] = s[(length - 1) - index], s[index]

Rather than indexing by (length - 1) - index, note that e.g. s[-1] is the last item in the list, s[-2] the penultimate item, and so on. So you can rewrite:

s[(length - 1) - index]

as:

s[-index - 1]

and we're now down to:

s[index], s[-index - 1] = s[-index - 1], s[index]

and there's no need to calculate length.


For the iterative version I would factor out median, too, going from:

median = len(s)//2
for index in range(median):
    ...

to simply:

for index in range(len(s) // 2):  # note whitespace
    ...

Although it's now factored out, note that:

median = len(s)//2
length = len(s)

could be rearranged to:

length = len(s)
median = length // 2  # and here

len(s) is O(1), but why duplicate it? DRY!


As I've previously shown, adding an extra parameter with a default value (def reverse_list_recur(s, index=0):) can simplify recursive approaches, removing the need for a nested function.

I would also remove the closure on median and explicit return/else and just test if index < len(s) // 2: before the swap:

def reverse_list_recur(s, index=0):
    """Reverse the contents of the list s and return None.

    >>> digits = [6, 2, 9, 5, 1, 4, 1, 3]
    >>> reverse_list_recur(digits)
    >>> digits
    [3, 1, 4, 1, 5, 9, 2, 6]
    >>> d = digits
    >>> reverse_list_recur(d)
    >>> digits
    [6, 2, 9, 5, 1, 4, 1, 3]
    """
    if index < len(s) // 2:
        s[index], s[-index - 1] = s[-index - 1], s[index]
        reverse_list_recur(s, index+1)

Depending on how you interpret "built-in list methods", the following may be OK:

def reverse_list(s):
    s[:] = s[::-1]
\$\endgroup\$
3
  • \$\begingroup\$ I don't know why I repetitively write the base case(index == median) in recursive approach, when it is not required!!! \$\endgroup\$ May 16 '15 at 11:54
  • \$\begingroup\$ @overexchange generally, if you find that an if block is trivial (just a return, in your case) think about whether you could reorder the conditions to factor it out. \$\endgroup\$
    – jonrsharpe
    May 16 '15 at 12:06
  • \$\begingroup\$ Yes I kept this point in mind, when you answered my previous questions, I again missed it while writing this code. \$\endgroup\$ May 17 '15 at 4:11
3
\$\begingroup\$

Since you seem to be fond of functional solutions without state changes, here's such alternative recursive implementation for reversing a list:

def reverse_list(lst):
    def reverse_list_recur(remaining, acc):
        if remaining:
            head, tail = remaining[0], remaining[1:]
            return reverse_list_recur(tail, [head] + acc)
        else:
            return acc
    lst[:] = reverse_list_recur(lst, [])

The recursive function accumulates a reversed version of the list, by prepending the first element of the remaining list in front of the accumulator. By stacking the first elements up this way, the end result is reversed order. The only mutation (state change) in this approach is the final step of replacing the content of the original list, as per the requirement.

In terms of space, this solution is not as efficient as reversing in-place, but perhaps it's more elegant.

\$\endgroup\$
0
\$\begingroup\$

median is a confusing variable name, as it has a very specific meaning that does not apply here (unless the list contains sorted data). A better name would be middle, or just mid.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.