Search

How To Reverse List In Python: 4 Techniques

Very often I get people asking me to write a post on how to reverse a list in python. This is because this question often comes up in interviews. So, to oblige them, I have decided to write on four good and tested ways you can reverse a list in python. I also show their timing so that you can choose the best for your needs.

 

python reverse list

The built-in python reversed function

The syntax of the built-in python reversed function is reversed(seq). You can see that it takes in any sequence as argument. Sequences are lists, strings, tuples etc. For a refresher on sequences, see my post on iterables. The function returns an iterator. Remember that an iterator is an object that has elements but in order to extract the elements you need to cast it to list or call the next method. Most times, you cast it to a list to get out the elements. But casting afterwards to a list for this method of reversing could be an overhead cost for the method although it is easy, and uses substantially less memory unless you are casting. This method is ideal for times when you are dealing with very large lists and just want to use the elements of the reversed list when needed rather than using all at once. In this instance, you would need to use a python for loop.

Let’s take an example:

You can see from the above that I had to cast the iterator from the python reversed function to a list to get out the results. That could be an overhead as we’ll see later.

The python slice technique

Slicing a sequence is one of the ubiquitous techniques you can find with python lists and sequences. The syntax of slicing is [start:stop:step] where start is the index you want to start the slice, stop is where you want to stop the slice and step is the steps you want to take when iterating through the list to create the slice. To reverse a list using the python slice technique, you just need to use this statement: list_name[::-1], which is a shorthand for saying copy the list and then walk through it backwards.

Here is an example:

The advantage of this technique is that it is adaptable for any sequence and not just for lists. Some people claim that it is not readable but I find that argument obscure. Slicing is common in python even for the beginner. The only disadvantage I see with the python slice technique is that it uses up memory if you have a large list. This is because to create the reversed list, it needs to copy the original list and then reverse it. This sequence takes up a large chunk of memory. But when you want the original list to remain unchanged, this technique is good and recommended.

The python list reverse method

The python list reverse method is a method of the list class. The syntax is list.reverse(). In my opinion, it seems to be the easiest since it is built for lists and seems to be the fastest so far. But we will consider that in the timing section below. Unlike in the built-in python reversed function, it does not create any overhead and unlike the slicing technique, it does not require large chunk of memory even when working with large lists. It is more optimized for reversing python lists.

The advantageous fact about it is that it reverses in place. But if you want to make use of the original list after reversing, then this technique is not for you.

Here is an example:

I usually use this technique whenever I am reversing lists but if I need the original, I use the slice technique. Just to make you know.

Reverse list programmatically by swapping items

Now the last method you can use is to reverse the list programmatically by swapping items in place. You can write your own code that iterates through the elements of the list and swaps the elements in place. Here is a sample code:

This code can run fast but is not optimized for large lists. It swaps the elements in place and modifies the original list. It is worse than all the python built-in methods.

Timing the methods.

Most times when we are dealing with large lists, we want something that works very fast and doesn’t use much memory. Although with the built-in timing functions in python we cannot calculate for memory usage, but we can find out how long it takes each of the techniques above to run. We will need to import the timeit module to do this.

Here is a sample code for all three built-in methods except the programmed reverse list swapping method. The swapping technique takes a longer time for large lists that is why it is excluded.

When you run the code above, you will see that the list reverse method takes the shortest time of all three methods. Overall, its running time is 12 times lesser than the reversed method. The reversed function took longer time because of the list casting overhead. If we had a for loop, it would have taken less time. The slicing technique comes second place. So, that is why I use the python list reverse method often when reversing lists.

The list reverse method works better because it has been optimized by the developers of python for lists. I believe they look to these things that is why it was made to be a method of the list class.

So, now you have the options you can choose from while reversing lists. Use any to your heart’s desire.

Happy pythoning.

The 0/1 Knapsack Problem In Python Simplified

When I wrote a post about an idea I had at a bank about making change from $5 and $8, a reader wrote me that this was the knapsack problem. I decided to research it. I discovered that although my post was not a knapsack problem, it was somewhat similar because it involved resource optimization. So, intrigued by the knapsack problem, I decided to write code on the 0/1 knapsack problem.

0/1 knapsack problem in python

 

What is the 0/1 knapsack problem?

The knapsack problem was stated using a burglar and how difficult it is being a burglar especially when you are greedy. Imagine a burglar breaks into a home carrying a knapsack with a fixed capacity. What he can steal is limited by the capacity of the knapsack. But the problem is that the items in the home have more value than what his knapsack can carry. So, he has a decision problem. What would he decide to take that would fit into his knapsack? In this problem, he cannot take pieces of items but he either chooses to take the item completely or leaves it (that is why it is called the 0/1 knapsack problem). How does the burglar decide on what to choose?

Let’s take an example of the items the burglar might find in the home. For example, the items he might need to choose from might be a clock, painting, radio, vase, book and computer with values and weight like in the table below:

Name Value Weight Value/Weight ratio
Clock 175 10 17.5
Painting 90 9 10
Radio 20 4 5
Vase 50 2 25
Book 10 1 10
Computer 200 20 10

Which items would he decide to take? We are going to analyze what options the burglar can make.

Why being greedy might not be optimal here.

The burglar has three dimensions of greed in making a choice. He would choose the best item first, then the next best, and so on until he reaches the limit of his knapsack. But what would best mean for him? Could it mean the most valuable, the least weight, or the highest value/weight ratio? Let’s give a value to the capacity of his knapsack and say he can only take items up to 20 kg. So, given a knapsack of 20 kgs, what combination of items can he take?

A stupid burglar or one in a hurry would just pick the computer and say that would give him the best value. But that is not the case. An intelligent burglar would go through his value system and decide what is best for him. But he doesn’t have all the time in the world. So, on the spur he chooses what is best based on his greed and picks accordingly. He has three dimensions of greed to choose from: based on value, based on least weight, and based on the density or value to weight ratio of the items.

I have written here a little code based on the greedy algorithm. It is named my_greed.py.To make the decision, the burglar would have to sort the items ranking them in order and picking each item until he exhausts his knapsack. You can download the code and run it on your machine and test it to see the solutions he would get for his greed.

If you run it you would get the following results. Based on values, if he picks the clock, radio and book, he would steal items that are worth 275. If he decides based on weight, he would pick the book, vase, radio and painting which are all worth 170. If he decides based on density or value to weight ratio, he would pick the vase, clock, book and radio which are all worth 255. So, the best solution for the burglar on the spur is to pick based on value where he gets a total value of 275. Unfortunately, because of greed, some burglar would just pick the computer which is only worth 200.

But choosing based on greed is not always the optimal solution. The burglar wouldn’t be able to consider all the possibilities of his choice. So, that is why I am not explaining the code for greed on this post. You need to study it to understand it yourself. I want to dwell on using the optimal solution.

The optimized algorithm for the knapsack problem.

I thought carefully about this problem and decided that the best and optimal solution for the burglar is to do the following (but he wouldn’t have all the time in the world):

1. Enumerate all the possible combination of items.

2. Remove all the combinations whose weight exceeds the capacity of the knapsack.

3. From the remaining combinations, choose any whose value is the highest.

So that is the focus of this blog. Using an optimal algorithm in getting a solution to the 0/1 knapsack problem. We will go through all the steps above one after the other using code. I hope you ride along.

First, we need to create the class for the items.


# create the items class
class Items(object):

    def __init__(self, name, value, weight):
        self.name = name
        self.value = value
        self.weight = weight

    def get_name(self):
        return self.name

    def get_value(self):
        return self.value

    def get_weight(self):
        return self.weight

    def __str__(self):
        result = f'{self.name}: Value = {self.value}. 
                          Weight = {self.weight}.'
        return result    

In the constructor, each item instance has a name, value and weight. Then there are the getters for the attributes. Then the last method is the __str__() method that specifies how to represent each object on the output.

Then the next thing to do is to build the Items into a list. With the list of items, we can create a superset later.


# build the items in a list
def build_items():
    names_list = ['Clock', 'Painting', 'Radio', 'Vase', 
                                   'Book', 'Computer']
    values_list = [175, 90, 20, 50, 10, 20]
    weight_list = [10, 9, 4, 2, 1, 20]
    collection = []
    for i in range(len(names_list)):
        collection.append(Items(names_list[i], values_list[i], 
                                              weight_list[i]))
    return collection

I created a separate list for each attribute and then in the for loop I created each item instance with their data. Then returned the list, collection.

Now that we have all data items in a list, we now need to enumerate all possible combinations of the items.


# create the powerset
from itertools import combinations, chain

def powerset(iterable):
    s = list(iterable)
    # powerset removes the empty set
    return list(chain.from_iterable(combinations(s, r) 
                         for r in range(1, len(s)+1)))

Notice that I imported the combinations and chain methods from itertools to create the powerset. It’s very easy. If you want an explanation of what was involved in creating the powerset, just read this blog post on combinations.

Then the last two activities to do is to remove all combinations whose total weight exceeds the capacity of the knapsack. When we have done that, from the remaining combinations, find out which of them gives us the maximum value because now all the remaining combinations can fit into the knapsack. This code does both activities.


# the main code
def choose_best(pset, max_weight):
    best_val = 0.0
    best_set = None
    for items in pset:
        items_val = 0.0
        items_weight = 0.0
        for item in items:
            items_val += item.get_value()
            items_weight += item.get_weight()
        if items_weight <= max_weight and items_val > best_val:
            best_val = items_val
            best_set = items
    return (best_set, best_val)

Now let me explain the code a little. The arguments to the choose_best method are powerset and max_weight, which is the weight of the sack. I then initialized best_val to capture the highest value among the combinations and best_set, to capture the best combination. Then in the outer for loop, I initialized the variables items_val and items_weight which are used as total values and total weights for each combination. Then in the inner for loop I iterate through each of the items in any chosen combination, getting their total value and total weight. Then, what I did next is check for whether the total weight, items_weight, is less than or equal to sack weight, the max_weight, and also if the total value, items_val, is greater than any other total value in previous combinations, if both cases are true, then it sets the total value, items_val, as the best value, best_val and tags this combination of items, best_set as the chosen combination. It then returns the best value, best_val, and the chosen combination, best_set, as a tuple.

Now the code to test the main code.


# code to test
def test_best(max_weight=20):
    items = build_items()
    pset = powerset(items)
    taken, val = choose_best(pset, max_weight)
    print('Total value of items taken is', val)
    for item in taken:
        print(item)

Since the weight of the knapsack is 20 kg, I set the max_weight as default of 20. You can specify something else when you are running the code. Then in the body of the function I built the items or collect the items into a list, then create the powerset of all the items. After that, I called the choose_best method to make the optimal choice or solution. Then in the final part of the code I use a for loop to print out each of the items that were in the chosen combination.

Here now is the complete program so you can run it here.

If you desire to study it in-depth and also run it on your own terminal, here is the download file, my_items.py.

That’s it. It’s fun coding the 0/1 knapsack problem. I hope you enjoyed it. I did.

You can leave comments below. Also, subscribe to my blog so that you can receive latest updates.

Happy pythoning.

Python Combinations Function – The Power To Choose

Let’s imagine this scenario. You are a fund manager who is in charge of several stocks. Your company has given you about 20 stocks to evaluate and asks you to find out what 5 stocks from the 20 you can include in your portfolio this year. You have a choice of selecting the 5 stocks which have equal probability of success. How many different selections can you make?

Ever seen a problem like this in college mathematics? Yes, it is an example of a combination problem. We see it all the time in life. In choosing what clothes to wear for the week, what combination of food to choose from a menu, or what combination of channels to watch for the week. We cannot do without combinations.

python combinations function

 

In simple terms, combinations can be defined as the number of possible arrangements you can make from a collection of items where the order of the selection does not matter. Combination is different from permutations because in permutations the order of selection matters.

Let me not bore you with the mathematical details. Let’s go straight to how python allows you to use the power of combinations.

How Python combinations work

To carry out combinations in python you need to import one function, the combinations function from the python itertools module. You can use the code: from itertools import combinations. Very simple. With that you are good to go.

The syntax for the python combinations function is: itertools.combinations(iterable, r) where iterable is the collection you want to select from and r is the number of possible arrangements you want to make from the collection. Note that r should not be greater than the length of the iterable otherwise python combinations function will return an empty object. When you call the combinations function, it returns a combinations object which is an iterator. You can cast the iterator to a list or set to extract the elements of the combination or the arrangements.

Now that the syntax is done, let’s solve the fund manager’s problem we started with.

The problem the fund manager is faced with is that out of 20 stocks he has to select 5 without order since they are all equally probable of success. How many selections or arrangements can he make?

I have included comments in the code above so you can follow along on the logic behind how it was applied. On line 1, we imported combinations from itertools module. That means we are good to go. On line 3, using range function, we created a collection or sequence of 20 items. So easy. On line 4 we called the combinations function and passed the collection or sequence as its first argument and then 5, the arrangements we are making, as its second positional argument. The python combinations function returned a combinations object which is an iterator, and in the next line we cast the iterator to a list so we can extract the items in it. But not to worry, we are not investing in any of the stocks yet, we just want to know how many selections the fund manager can make. So, on the last line we called length function on the list and it gave us the answer: 15504 possible arrangements of the stocks. I bet, the fund manager needs more than a voodoo priest to decide on what arrangement of stocks to choose.

I believe that right now you understand how the python combinations function works. But am not going to leave you without one more example. I so love this one because I use it often on a weekly basis.

For example, Michael loves eating 5 types of foods but he can only choose three of them every day. If the order he chooses each meal is not important, how does he choose. Also, how many choices can he make? This is just easy, right? Let’s do it.

It’s so easy, not so? I believe you can read and follow along with the code above. It’s one of the easiest codes I’ve written this week. If you look at the food choices, you would notice that rice stands out prominently. Well, because order doesn’t matter it makes no difference if rice is at the beginning of a choice or the end for each day. Why you get the print out is because combinations prints out the arrangements based on the order it finds the items in the sequence or collection. If you want a different order, you can sort the food list. Try it out on your machine and see.

Now, let me give you a bonus tip. The combinations function in python makes it possible for you to do a calculation that before now took a very lot of processing to carry out. That is calculating the powerset of a set. Before I discovered the combinations function, I used to calculate powerset of a set based on an algorithm that was of exponential complexity. You get what I mean? It took a lot of time but when I discovered combinations function, all that stress was put to rest.

How to calculate powerset of a set using python combinations function.

The powerset of a set, S, can be defined as the set consisting of all subsets of S, including the empty set and S itself. So, that’s the mathematical definition and that is the result we expect to have in our code.

To get the powerset of any iterable from the combinations function, we will use the following code:


from itertools import combinations, chain

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) 
                      for r in range(len(s)+1))

Notice that this time we are not only importing combinations but also the chain function. The meat of the code lies in the last line of the powerset function. What is happening there is that using a generator expression we are creating combinations with the arrangements, r, going from 0 , 1, 2… to the length of the iterable. This makes sure we are creating arrangements for every combination of the powerset. The generator expression outputs a combination object which is an iterator. To extract the elements we have to cast it to a chain object, which is also an iterator and then cast the result of the function to a list or any other iterable. The casting to a list was done in the example below. Note that the elements will be arranged in tuples since they are combinations of sometimes more than one object. It’s so elegant. No more lengthy and time consuming code.

Let’s try it with a working example.

The code above will print out the powerset of the list, num. Cool, right?

Experiment with these functions to your heart’s delight. They demonstrate the power of python.

Happy pythoning.

Matched content