Hello,
I’d like to select a specific permutation of a list with some items (>10).
I’d like to iterate through these permutations in order to find the ones which fulfill certain constraints.
I’ve tried to use the permutations function from itertools in order to get the permutations list and then iterate through this list of lists by an index. Unfortunately, it makes an error occur. I think it happens because of the huge number of permutations as items of the list: n! Where n is the number of items in the original list. Any ideas about how to solve or any alternative strategies?
From itertools import permutations
def spec_permutation(i,original_list):
ls = list(permutations(original_list))
return ls[i]
The error is: “anvil.server.ExecutionTerminatedError: Server code exited unexpectedly: 3c53b4cb75”
Welcome to the Forum, @gioelor .
Strictly speaking, this is a Python question, not an Anvil question. Any Python implementation is likely to raise an error when n gets large enough. After all, your code builds a list with n! elements, each of which takes up space.
Then it throws away all of the elements except the ith. Everything else it generates is a waste of space. Everything after the ith element is a waste of space and time.
Have a look at the Python standard library function enumerate. With that, you’d be able to stop at the ith value.
It depends on what you mean by “a specific permutation”.
Getting a random one is easy, no need to iterate.
Perhaps you can figure out a smart way to get to your permutation without iterating at all.
If you really want to play with the full list of permutations, one way to avoid memory problems could be to create an sqlite database in memory and execute a join query. Perhaps sqlite is smart and creating a query that searches from the result of a subquery that creates the permutations on the fly will be memory efficient.
Perhaps pandas could help too.
Thank you for your reply. I will try to use enumerate.
permutations returns a generator, which is safe to use regardless of the number of permutations. You’re getting into trouble because you’re converting it to a list. Instead do a for loop over the permutations and when you get to the index you want, return it.
1 Like
Thank you for your reply.
The reason why I am interested in iteration through permutations of a list of items is the following: I have a function (objective function) that takes in input one permutation of the original list and it returns a value that represents the score (rating) reached with that permutation. I have to find the permutation that leads to the best score of the objective function. In other words, it is an optimization problem where the order of the items in the original list is crucial to obtain different scores from the objective function. My first idea was to iterate through every permutations and classify them on the basis of the score that they produce. At the end of this process, I can see easily which is the “best” permutation by simply observe the returned values of the objective function. I know this is a brute-force approach since I’m trying to test every possible input and evaluate the relative outputs. Probably there are different better approaches. I need to look for optimizations problems and how to implement efficient searching algorithms.
Many thanks for your hint. I will try this solution.
If the problem is the lack of memory, evaluating the score of every permutation with the brute force could shift the bottleneck to the time required to evaluate all the permutations.
I hope I’m wrong 
Good luck!
You are really right. The problem is the time needed to evaluate the score of every possible permutation. So, waiting to find the best approach, I think that I will evaluate the objective function only in a subset of permutations that are the ones which have more possibilities to be the best rather than the others that I discard. I will try to find a reasonable way to discard large number of permutations which have lower chances to be the best one. Thanks again.
I don’t know what the values in the permutations mean, but if it helps, here is how I often do my optimizers: I use an evolutionary algorithm that starts with calculating the score of one solution, then applies some mutations to the DNA, in your case this could be swapping some values of the previous permutation, calculate the score, etc.
I keep the top x solutions, for example the 100 permutations with the best score, and at every iteration I pick one of them and apply a mutation. Rinse, repeat.
In order for this to work you need to:
- get the first DNA (permutation) that has good chances to be fairly good (better than average)
- use some logic for the mutation that has good chances of improving the score
- it could help applying a bias so it picks the solution for the mutation from closer to the top of the list
I usually set a time limit and pick the best solution when the time is over, or when there is no improvement after a certain time.
Thanks a lot for the hint.
This is a good strategy. Probably i will find local “optimal points” intead of the global “optimal point”, because i can’t assume that, when the set time will be over, there are no other better solutions that have been not explored. But it is for sure a good start.
In order to get out of local optimal points you can work on the mutation algorithm and get it to apply more or less often a more or less random change.
I sometimes have 3-4 strategies, one that will converge when I’m close to a maximum in certain conditions, one that converges in other conditions, one that is a wild guess, etc. The art is figuring out what strategies make sense and what percentage of tries each one should get.
For example when I optimize the material used to cut panels, basically I need to fit a number of small rectangles inside a smaller number of larger rectangles, valid strategies could be:
- repeat x times the y-th best sheet of material (it will work well if there are many same size panels)
- swap x panels of the y-th best sheet with x panels of the z-th best sheet (it will work with panels of similar but not identical size)
- create x random solutions (just to get out of a local maximum)
Very Good! I think that thanks to these suggestions i will be able to produce an effective algorithm for what i need.
Thank you again!