Is there a better way to use permutations?

Question

I need to make a data structure of permutations. Currently I am using a generator that is very time expensive. Is there an alternative to a generator or some other way to systematically step through different indices in for a matrix? The other problem might be the function that now takes the strings and makes them a list of lists.

This is for an assignment problem.

def ourpermutations(iterable, r=None):
    """
    Input:
    String or numbers separated by a space
    optional= the length that the permutations must be

    Output:
    a generator of permutations
    """

    pool = iterable.split(" ")
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

def ExhaustiveSearchinputs(datamatrix):
    """
    Input:
    datamatrix: numpy array

    Output:
    list of every permutation allowed and the time it took to run(this is to help with the optimisation and 
    testing process)

    """

    # Important starting values
    start = time.time()
    length = len(datamatrix)
    thestring = ""

    #Generate the permutations
    for i in range(0,length):  #this is making a string of numbers from 0 to the size of the matrix -1
        thestring += str(i) + " "
    thestring = thestring[:-1]
    listofassociations = list(ourpermutations(thestring,length))  #this was the function we made earlier

    #these are the time calculation
    end = time.time()
    thetime = end - start
    return listofassociations, thetime,thestring
##########PLEASE NOTE THIS FUNCTION TAKES 4 seconds once datamatrix is length 8 and takes 99 seconds for length 9

The output is correct just slow.

Have you tried the built in module itertools? Try reading on https://docs.python.org/2/library/itertools.html — Seraph Wedd, Jul 31 '19 at 08:20
As far as I can tell, your solution only works if the input list consists of unique elements. If you have two of the same, the length of the set will not be correct. — JohanL, Jul 31 '19 at 08:54

Paul Panzer · Answer 1 · 2019-07-31T10:10:21.923

The problem are not generators in general, but the one you are using.

Going through the full product and filtering out those tuples which are permutations is indeed extremely inefficient. The number of all tuples is N^N out of which N! are actual permutations. Let's compute the ratio N!/N^N for a few values of N: N=5: ~0.038; N=7: ~0.0061; N=10: ~0.00036; N=20: ~0.000000023. In other words, already at N=5 you are looping through 25 useless tuples for each good one.

Using Stirling's approximation we can see that the ratio is quite well approximated by sqrt(2 pi N) exp(-N).

Exponentially bad yield is, of course, completely unacceptable. So you will have to come up with a better enumeration strategy. Or use itertools.permutations.

Is there a better way to use permutations?

1 Answers1