# Task
 You are given a string `s`. Every letter in `s` appears once. 
 
 Consider all strings formed by rearranging the letters in `s`. After ordering these strings in dictionary order, return the middle term. (If the sequence has a even length `n`, define its middle term to be the `(n/2)`th term.)

# Example

 For `s = "abc"`, the result should be `"bac"`.
```
The permutations in order are:
"abc", "acb", "bac", "bca", "cab", "cba"
So, The middle term is "bac".```

# Input/Output


 - `[input]` string `s`

  unique letters (`2 <= length <= 26`)

 - `[output]` a string

  middle permutation.

Difficulty: interview

Starter code:

def middle_permutation(string):
	

Solutions:
def middle_permutation(string):
    s = sorted(string)
    if len(s) % 2 ==0:        
        return s.pop(len(s)//2-1) +''.join(s[::-1])
    else:
        return s.pop(len(s)//2) + middle_permutation(s)

def middle_permutation(s):
    s = ''.join(sorted(s))
    return s[len(s)//2-1:(len(s)+1)//2][::-1] + s[(len(s)+1)//2:][::-1] + s[:len(s)//2-1][::-1]

from math import factorial

def nth_permutation(s, n):
    if not s:
        return ''
    m = factorial(len(s)-1)
    q, r = divmod(n, m)
    return s[q] + nth_permutation(s[:q] + s[q+1:], r)        

def middle_permutation(s):
    return nth_permutation(sorted(s), factorial(len(s)) // 2 - 1)

def middle_permutation(s):
    s = ''.join(sorted(s, reverse=True))
    return s[ len(s)//2 : (len(s)+3)//2 ] + s[ :len(s)//2 ] + s[ (len(s)+3)//2: ]

def middle_permutation(string):
    s = "".join(sorted(string))
    mid = int(len(s) / 2) - 1
    if len(s) % 2 == 0:
        return s[mid] + (s[:mid] + s[mid + 1:])[::-1]
    else:
        return s[mid:mid + 2][::-1] + (s[:mid] + s[mid + 2:])[::-1]

def middle_permutation(string):
    letters = sorted(string, reverse=True)
    start = letters.pop(len(string)//2)
    if len(string) % 2:
        start += letters.pop(len(string)//2)
    return start + "".join(letters)

from math import factorial

# on factorial number system and its relation to lexicographically ordered permutations;
# https://medium.com/@aiswaryamathur/find-the-n-th-permutation-of-an-ordered-string-using-factorial-number-system-9c81e34ab0c8
# https://en.wikipedia.org/wiki/Factorial_number_system
def factoradic_representation(n):
    res = []
    i = 1
    while n > 0:
        res.append(n % i)
        n = n // i
        i += 1
    return res[::-1]

def middle_permutation(string):
    if len(string) < 2:
        return string
    s = sorted(string)
    res = []
    fr = factoradic_representation(factorial(len(s))//2-1)
    fr = [0] * (len(string) - len(fr)) + fr
    for idx in fr:
        res.append(s.pop(idx))
    return "".join(res)

def middle_permutation(string):
    rev, l = sorted(string)[::-1], len(string)
    mid = rev[l//2:l//2 + l%2 + 1]
    return ''.join(mid + [ch for ch in rev if ch not in mid])

def middle_permutation(s):
    s = ''.join(sorted(s))
    m = int(len(s) / 2)
    x = s[m-1:m+1] if len(s) % 2 else s[m-1]
          
    return (s.replace(x, '') + x)[::-1]

def middle_permutation(string):
    sortedString = ''.join(sorted(string))
    reversedString = sortedString[::-1]
    result = ''
    result += reversedString[int(len(reversedString)/2) : int((len(reversedString)+3)/2)]
    result += reversedString[0:int(len(reversedString)/2)]
    result += reversedString[int((len(reversedString)+3)/2):]
    return result