Optimization of Unique, non-reversible permutations in Python

Question

I'm currently trying to solve the 'dance recital' kattis challenge in Python 3. See here

After taking input on how many performances there are in the dance recital, you must arrange performances in such a way that sequential performances by a dancer are minimized.

I've seen this challenge completed in C++, but my code kept running out of time and I wanted to optimize it.

Question: As of right now, I generate all possible permutations of performances and run comparisons off of that. A faster way to would be to not generate all permutations, as some of them are simply reversed and would result in the exact same output.

import itertools
print(list(itertools.permutations(range(2)))) --> [(0,1),(1,0)] #They're the same, backwards and forwards
print(magic_algorithm(range(2))) --> [(0,1)] #This is what I want

How might I generate such a list of permutations?

I've tried:

-Generating all permutation, running over them again to reversed() duplicates and saving them. This takes too long and the result cannot be hard coded into the solution as the file becomes too big.

-Only generating permutations up to the half-way mark, then stopping, assuming that after that, no unique permutations are generated (not true, as I found out)

-I've checked out questions here, but no one seems to have the same question as me, ditto on the web

Here's my current code:

from itertools import permutations

number_of_routines = int(input()) #first line is number of routines
dance_routine_list = [0]*10
permutation_list = list(permutations(range(number_of_routines))) #generate permutations

for q in range(number_of_routines):
    s = input()
    for c in s:
        v = ord(c) - 65
        dance_routine_list[q] |= (1 << v) #each routine ex.'ABC' is A-Z where each char represents a performer in the routine

def calculate():
    least_changes_possible = 1e9 #this will become smaller, as optimizations are found
    for j in permutation_list:
        tmp = 0
        for i in range(1,number_of_routines):
            tmp += (bin(dance_routine_list[j[i]] & dance_routine_list[j[i - 1]]).count('1')) #each 1 represents a performer who must complete sequential routines
        least_changes_possible = min(least_changes_possible, tmp)
    return least_changes_possible

print(calculate())

Edit: Took a shower and decided adding a 2-element-comparison look-up table would speed it up, as many of the operations are repeated. Still doesn't fix iterating over the whole permutations, but it should help.

Edit: Found another thread that answered this pretty well. How to generate permutations of a list without "reverse duplicates" in Python using generators

Thank you all!

sometimes using `combinations` are enough -not sure if it fits your bull - too tired. You can look into it: https://docs.python.org/2/library/itertools.html#itertools.combinations — Patrick Artner, Apr 11 '20 at 22:12
Thx @PatrickArtner. Hmmm maybe I'll use combinations to create a look-up table. That would speed it up — bethekind, Apr 11 '20 at 23:04

score 0 · Answer 1 · answered Apr 12 '20 at 02:15

There are at most 10 possible dance routines, so at most 3.6M permutations, and even bad algorithms like generate 'em all and test will be done very quickly.

If you wanted a fast solution for up to 24 or so routines, then I would do it like this...

Given the the R dance routines, at any point in the recital, in order to decide which routine you can perform next, you need to know:

Which routines you've already performed, because there you can't do those ones next. There are 2^R possible sets of already-performed routines; and
Which routine was performed last, because that helps determine the cost of the next one. There are at most R-1 possible values for that.

So there are at less than (R-2)*2^R possible recital states...

Imagine a directed graph that connects each possible state to all the possible following states, by an edge for the routine that you would perform to get to that state. Label each edge with the cost of performing that routine.

For example, if you've performed routines 5 and 6, with 5 last, then you would be in state (5,6):5, and there would be an edge to (3,5,6):3 that you could get to after performing routine 3.

Starting at the initial "nothing performed yet" state ():-, use Dijkstra's algorithm to find the least cost path to a state with all routines performed.

Total complexity is O(R²*2^R) or so, depending exactly how you implement it.

For R=10, R²*2^R is ~100 000, which won't take very long at all. For R=24 it's about 9 billion, which is going to take under half a minute in pretty good C++.

Optimization of Unique, non-reversible permutations in Python

I've tried:

1 Answers1