perm.py

def compute_perm_mapping(from_list, to_list):
    index = {}
    if len(from_list) == len(to_list):
        for i, x in enumerate(to_list):
            index.setdefault(x, []).append(i)
    
    try:
        mapping = [index[x].pop(0) for x in from_list]
    except (KeyError, IndexError) as _:
        raise ValueError('from_list is not a permutation of to_list')
    
    return mapping


def apply_perm_mapping(mapping, ys):
    n = len(ys)
    xs = [None] * n
    for i in xrange(n):
        xs[mapping[i]] = ys[i]
    return xs


# Properties:
def prop_apply_perm(xs):
    import random
    xs = list(xs)
    ys = xs[:]
    random.shuffle(ys)
    return apply_perm_mapping(compute_perm_mapping(ys, xs), ys) == xs

def prop_identity_map(xs):
    return compute_perm_mapping(xs, xs) == range(len(xs))