#!/usr/bin/env python
#-*- coding: utf-8 -*-
__author__ = 'francis'


def permute(xs):
    """Returns a generator for the permutations of elements in the sequence
    :param xs: a sequence of elements
    """
    if len(xs) == 1:
        yield xs
    else:
        for i in xrange(0, len(xs)):
            for p in permute(xs[0:i] + xs[i + 1:]):
                yield [xs[i]] + p


def longest_inc_seq(xs):
    """Finds the longest increasing sequences in the given sequence
    :param xs: a sortable sequence of elements
    """
    seq = []  # all increasing sequences
    indices = []  # indices of longest increasing sequences
    size = 0  # current longest size
    for i in xrange(0, len(xs)):
        for j in xrange(0, len(seq)):
            if xs[i] > seq[j][-1]:
                t = seq[j] + [xs[i]]
                if len(t) > size:
                    indices = [len(seq)]
                    size = len(t)
                elif len(t) == size:
                    indices.append(len(seq))
                seq.append(t)
        seq.append([xs[i]])
    return [seq[k] for k in indices]


def longest_common_seq(first, second):
    """Find the longest common sequence of the given sequences
    :param first: the first sequence
    :param second: the second sequence
    """
    res = []
    for i in range(0, len(first)):
        for j in range(0, len(second)):
            if second[j] == first[i]:
                t = [first[i]] + longest_common_seq(first[i + 1:], second[j + 1:])
                if len(t) > len(res):
                    res = t
    return res


def fib(n):
    """Computes the fibonacci number for the given term
    :param n: the term of the fibonacci sequence
    """
    if not n:
        return 0

    previous = 0
    current = 1
    while n - 1:
        current, previous = (previous + current), current
        n -= 1
    return current