1. 求一个数的阶乘

def factorial(n): 

    if n == 1:

        return 1

    else:

        return n * factorial (n-1)

2. 求任意输入字符的全排列

def permutation(xxs, y):

"""

: xxs: 已经排好的序列list，例如["ab", "ba"]

: y : 新添的元素，例如'c'

: return: yys: 新的序列list，例如["cab", "acb", "abc", "cba", "bca", "bac"]

    """

    yys = []

    for xx in xxs:

        for i in range(len(xx) + 1):

            yy = "{}{}{}".format(xx[:i], y, xx[i:])

            yys.append(yy)

    return yys

def full_permutation(s):

    yys = []

    if len(s) > 1: 

        yys = permutation(full_permutation(s[:-1], s[-1]))

    else:

        yys = [s]

    return yys

# Test

test_str = "abc"

new_str = full_permutation(test_str)

new_str结果 = ['cba', 'bca', 'bac', 'cab', 'acb', 'abc']

3. 求两个有序数列的并集

例如，A = [2, 4, 4, 6, 9], B = [4, 5, 7], 输出[2, 4, 5, 6, 7, 9]

注意A和B中可能会有重复元素

def union(A, B):

    C = []

    c = None

    cc = None    # Candidate of c

    ia, ib, ic = 0, 0, 0

    while (ia < len(A) and ib < len(B)):

        if A[ia] <= B[ib]:

            cc = A[ia]

            ia += 1

        else:

            cc = B[ib]

            ib += 1

    # 去重复

    if cc != c:

        c = cc

        C.append(c)

    # 看A或B是否还有残余

    if ia <= len(A):

        if A[ia] != c:

            c = A[ia]

            C.append(c)

        ia += 1

    elif ib <= len(B):

        if B[ib] != c: 

            c = B[ib]

            C.append(c)

    return C