Ranking permutations recursively in python

Question

How can I format this function so that it works recursively? I want to go multiple levels deeper if possible, not just until 5.

permutations is a list with different permutations, and those individual permutation can also have permutations, etc. I want to rank them based on some calculations I do in get_permutations and return the new order of permutations. A good way to look at it is probably a large list of lists of lists of lists of lists. First I want to change the order of the first level, than one step deeper etc. But eventually I return the string based on those permutations and not the permutation itself (if that matters), with res1...res5 being the strings. I'm not smart enough to get it to work recursively, even though I know it should be possible...Any ideas?

permutations, res1 = get_permutations(str, 1)

for p2 in permutations:
    permutations_2, res2 = get_permutations(p2,2)

        for p3 in permutations_2:
            permutations_3, res3 = get_permutations(p3,3)

            for p4 in permutations_3:
                permutations_4, res4 = get_permutations(p4, 4)

                for p5 in permutations_4:
                    permutations_5, res5 = get_permutations(p5,5)

                res4 += res5
            res3 += res4    
        res2 += res3    
    res1 += res2

return res1

EDIT: this returns a single (best) permutation. That is what the result is for. So not a list of possible permutations, as mentioned in the answers. E.g. if we have a lists of lists of lists, if first sorts the list based on all subinformation, then sorts the multiple lists of lists based on the previous sorts and all subinformation and then sorts the lists of lists of lists based on the previous 2 sorts.

Possible duplicate of [Python permutations recursive](http://stackoverflow.com/questions/35814976/python-permutations-recursive) — user2390182, Jan 23 '17 at 14:28

user2390182 · Answer 1 · 2017-01-23T14:38:08.033

A recursive generator function that yields permutations in the expected order with regard to the original string:

def get_permutations(a):
    if len(a) <= 1:
        yield a
    else:
        for i in xrange(len(a)):
            for p in get_permutations(a[:i]+a[i+1:]):
                yield ''.join([a[i]])+p

>>> a = '123'
>>> list(get_permutations(a))
['123', '132', '213', '231', '312', '321']

The recursive principle here:

Base case: strings of lengthes (0, 1) have only one permutation: themselves.
Recursion: for each letter in the string, remove it and prepend it to each permutation of the string's remainder.

score 0 · Answer 2 · edited May 23 '17 at 12:01

An example below, This method works by nesting for loops in a recursive manner repeat-times. We then accumulate the result of the sub-solutions, appending to a result list:

result = []
def permutations(alphabet, repeat, total = ''):
    if repeat >= 1:
        for i in alphabet:
            # Add the subsolutions.     
            permutations(alphabet, repeat - 1, total + i)  

    else:
        result.append(total)
    return result

Sample Outputs:

permutations('ab', 3) ->
$ ['aaa', 'aab', 'aba', 'abb', 'baa', 'bab', 'bba', 'bbb']
permutations('ab', 3) ->
$ ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa',
  'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 
  'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
permutations('ab', 1) ->
$ ['a', 'b']

Source: a previous answer of mine.

Ranking permutations recursively in python

2 Answers2