3

Started to learn programming 2 months ago, in one of my little projects i encountered the need to generate permutations of list of objects. I knew that i'll find how to do this if i'll just searched for it, but i wanted to make one of my own, so i worked up and made my own permutation generator code:

def perm(lst, c = [], x = 0):
    i = -1
    g = len(lst) - 1
    if x == g:
        while i < g:
            i += 1
            if lst[i] in c:
                continue
            c.append(lst[i])
            print(c)
            del c[-1]
            i = g
    else:
        while i < g:
            if x == 0:
                del c[:]
            elif g == x:
                del c[-1]
            elif len(c) > x:
                del c[-1]
                continue
            i += 1
            if lst[i] in c:
                continue
            c.append(lst[i])
            x + 1
            perm(lst, c, x + 1)

This is what it gives if i run it:

perm(range(2))
[0, 1]
[1, 0]

perm([1, 4, 5])
[1, 4, 5]
[1, 5, 4]
[4, 1, 5]
[4, 5, 1]
[5, 1, 4]
[5, 4, 1]

It works as i expected, but when i use bigger lists it take some time for it to generate all the permutations of the list. So all i want is hints on how to improve my code, only hints. Or if you can tell me what should i learn to be able to make a better generator?

Thanks in advance for all the helpers.

Improve this question

6 Answers 6

Reset to default
3

Generating permutations is often done recursively. Given a list of 5 items, the permutations can be created by picking each of the 5 elements in turn as the first element of the answer, then for each of them permuting the remaining 4 elements, and appending them together.

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

Comments

3 
>>> from itertools import permutations
>>> list(permutations(range(2)))
[(0, 1), (1, 0)]
>>> list(permutations([1, 4, 5]))
[(1, 4, 5), (1, 5, 4), (4, 1, 5), (4, 5, 1), (5, 1, 4), (5, 4, 1)]

In the docs there is Python code available for legacy versions.

A note re your code, x + 1 doesn't do anything as you're not assigning result of that expression to anyting.

Improve this answer

7 Comments

Thanks, but if you really read my post till the end you would notice that i am not searching for a way to do it, but for a hint on how to improve my own code. Or what should i learn to be able to improve it.
@just: do you want to have your code to run in a constant time no matter input? What is your aim?
@justesting: The way to make it better is to use the standard library that already has it implemented.
I certainly understand your desire to learn, but this answer definitely deserves credit for helping you learn that python comes with a best way to do things. +1
Also, you can just read the code in the standard library and learn from that. In the case of itertools, you don't even have to look at the source - the docs have it, too: docs.python.org/library/itertools
|
2

The best way to understand what is making your code slow is to actually measure it. When you attempt to guess at what will make something fast, it's often wrong. You've got the right idea in that you're noticing that your code is slower and it's time for some improvement.

Since this is a fairly small piece of code, the timeit module will probably be useful. Break the code up into sections, and time them. A good rule of thumb is that it's better to look at an inner loop for improvements, since this will be executed the most times. In your example, this would be the loop inside the perm function.

It is also worth noting that while loops are generally slower than for loops in python, and that list comprehensions are faster than both of these.

Once you start writing longer scripts, you'll want to be aware of the ability to profile in python, which will help you identify where your code is slow. Hopefully this has given you a few places to look.

Improve this answer

2 Comments

Thanks a lot, i don't know how to give credit, and i think that i can't cause i am not registered! I would love to see more of those answers, i really appreciate your help.
Registered, and thanks. Your answer alongside mfukar answer gave me a new level of understanding on the subject.
1

OK, for large lists, a recursive solution will take more and more time & space, and eventually reach the recursion limit and die. So, on the theoretical side, you could work on ways to save time and space.

Hint: tail-recursive functions (such as the one you've written) can be rewritten as loops

On a more practical side, you may consider the use cases of your function. Maybe there's somebody who doesn't want the whole list of permutations at once, but a single one each time - there's a good opportunity to learn about yield and generators.

Also, for something generally not directly applicable to your question: k-combinations and multisets are closely related to permutations. Perhaps you can extend your function (or write a new one) which will produce the k-combinations and/or multiset the user asks for.

Improve this answer

1 Comment

Another facinating answer, Thanks A LOT!
0

The first thing I notice is that the code is hard to understand. The variable names are completely meaningless, replace them with meaningful names. It also seems like you're using i as a loop index, which is almost always bad style in python, because you can do for item in list:.

Improve this answer

Comments

0

This is not really performance related, but there is a glaring bug in the code. Using a list as a default parameter does not do what you think it does - it will create one list object that will be shared by every call to perm(), so the second time you call perm you will have the value in c of whatever it contained when the last call finished. This is a common beginner's error.

You also say "when I use bigger lists it takes some time to generate all the permutations of the list". What did you expect? The number of permutations is equal to the factorial of the length of the list, and that grows big fast! For example a list of length 20 will have 2432902008176640000 permutations. Even the most efficient algorithm in the world is "going to take some time" for a list this size, even if it did not run out of memory first. If our hypothetical algorithm generated a billion permutations a second it would still take 77 years to run. Can you be more specific about the length of lists you are using and how long it is taking?

Improve this answer

4 Comments

Thanks for the info, I'll appreciate it if you'll be able to explain the glare thing. Anyway currently my code can handle lists of length 8 in 1second or less, but when i try to generate permutations of list of length 10 it takes 25 seconds or so. But i think that i have a general idea that will improve my code.
Ok i understood what you meant. Changed it to perm(lst, x + 1), Thanks for pointing this out.
Ok timed it and it takes more than 25 seconds with a list of length 10, it takes 59 seconds or so. Anyway working on a better code right now.
10! is 3628800, so if it takes 59 seconds then it is producing 61505 permutations per second. most of this time is probably spent allocating and freeing memory in your list - it is far more efficient to use a generator to return the result one at a time instead of in a huge list. It will also use far less memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.