def sublists(L, m):
    """Επιστρέφει το πόσες υπολίστες της L έχουν άθροισμα στοιχείων m. Υποθέτουμε ότι όλα τα στοιχεία της L είναι
    διαφορετικά"""
    if len(L)==0: # Αν η λίστα L είναι κενή τότε μόνο στην περίπτωση που το m είναι 0 υπάρχει υπολίστα με άθροισμα στοιχείων m
        if m==0:  #  και μάλιστα μόνο μια υπολίστα, η κενή. Αν m δεν είναι 0 και η L είναι κενή τότε η απάντηση είναι 0.
            return 1
        else:
            return 0
    # Από τις υπολίστες με άθροισμα στοιχείων m άλλες περιέχουν το L[0] κι άλλες όχι.
    # Αυτές που δεν περιέχουν το L[0] είναι όλες οι υπολίστες της υπόλοιπης λίστας L[1:] που έχουν
    # άθροισμα m (δεύτερος όρος στο άθροισμα παρακάτω, που υπολογίζεται με αναδρομική κλήση).
    # Αυτές που περιέχουν το L[0] είναι όλες οι υπολίστες της L[1:] με άθροισμα m-L[0] (πρώτος
    # όρος στο παρακάτω άθροισμα που υπολογίζεται αναδρομικά).
    return sublists(L[1:], m-L[0]) + sublists(L[1:], m)



def whichsublists(L, m):
    """Επιστρέφει μια λίστα που περιέχει όλες τις υπολίστες της L έχουν άθροισμα στοιχείων m.
    Υποθέτουμε ότι όλα τα στοιχεία της L είναι διαφορετικά"""
    if len(L)==0: # Αν η λίστα L είναι κενή τότε μόνο στην περίπτωση που το m είναι 0 υπάρχει υπολίστα με άθροισμα στοιχείων m
        if m==0:  #  και μάλιστα μόνο μια υπολίστα, η κενή. Αν m δεν είναι 0 και η L είναι κενή τότε η απάντηση είναι [].
            return [[]] # μόνο μια υπολίστα της L υπάρχει που πληροί τα κριτήρια, η κενή
        else:
            return [] # καμία υπολίστα της L δεν πληροί τα κριτήρια
    # Από τις υπολίστες με άθροισμα στοιχείων m άλλες περιέχουν το L[0] κι άλλες όχι.
    # Αυτές που δεν περιέχουν το L[0] είναι όλες οι υπολίστες της υπόλοιπης λίστας L[1:] που έχουν
    # άθροισμα m (δεύτερος όρος στη συνένωση λιστών στο return παρακάτω, που υπολογίζεται με αναδρομική κλήση).
    # Αυτές που περιέχουν το L[0] είναι όλες οι υπολίστες της L[1:] με άθροισμα m-L[0]
    # (λίστα l2 που υπολογίζεται αναδρομικά).
    l1 = whichsublists(L[1:], m-L[0])
    l2 = []
    for x in l1:
        l2.append([L[0]]+x) # Τα στοιχεία της l2 είναι ακριβώς αυτά της l1 αλλά τους έχει προστεθεί και το L[0]
        
    return l2 + whichsublists(L[1:], m)

whichsublists([-1,0,1,2,3], 0)

def fib(n):
    if n == 1 or n == 2:
        x = 1
    else:
        x = fib(n-1) + fib(n-2)
    return x

for i in range(1,11):
    print "F({i}) = {value}".format(i=i, value=fib(i))

def fib(n):
    print "Computing fib({n})".format(n=n)
    if n == 1 or n == 2:
        x = 1
    else:
        x = fib(n-1) + fib(n-2)
    return x

x=fib(5)
print "F(5)=",x

def fib(n):
    global di
    print "Computing fib({n})".format(n=n)
    if n == 1 or n == 2:
        x = 1
    else:
        y = di[n-1] if (n-1) in di else fib(n-1)
        z = di[n-2] if (n-2) in di else fib(n-2)
        x = y+z
    
    di[n] = x
    return x

di = {}
x = fib(10)
print "F(10)=",x

import random
import time

def binsearch(x, L):
    """ Δυαδικό ψάξιμο του ακεραίου x στην ταξινομημένη σε αύξουσα σειρά λίστα ακεραίων L.
    Επιστρέφει μια θέση του x, ή -1 αν δεν υπάρχει. Χωρίς αναδρομή. """
    N = len(L)
    low = 0
    high = N-1
    while high > low+10:
        m = (low+high)/2
        y = L[m]
        if x == y:
            return m
        if x<y:
            high = m
        else:
            low = m
    for i in range(low, high+1):
        if L[i] == x:
            return i
    return -1

def recbinsearch(x, L):
    """ Δυαδικό ψάξιμο του ακεραίου x στην ταξινομημένη σε αύξουσα σειρά λίστα ακεραίων L.
    Επιστρέφει μια θέση του x, ή -1 αν δεν υπάρχει. Γραμμένο ως αναδρομική συνάρτηση. """
    N = len(L)
    
    if N<10: # Αν η λίστα είναι μικρή την ψάχνουμε σειριακά
        for i in range(N):
            if x == L[i]:
                return i
        return -1
    
    # Αλλιώς χωρίζουμε τη λίστα σε δύο μισά και, ανάλογα με το πώς συγκρίνεται το x με την τιμή
    # στο μέσο της λίστας, ψάχνουμε το αριστερό ή το δεξί μισό καλώντας αναδρομικά την ίδια συνάρτηση.
    m = N/2
    y = L[m]
    if y == x:
        return m
    if y>x:
        return recbinsearch(x, L[:m])
    return recbinsearch(x, L[m:])

# Φτιάχνουμε μια τυχαία λίστα ακεραίων και την ταξινομούμε κατά αύξουσα σειρά
l = []
N = 100000
for i in range(N):
    l.append(random.randint(1, 100*N))
l.sort()

x = 100*N+1 # Αυτή η τιμή σίγουρα δεν είναι μέσα στη λίστα l
t1 = time.time()
binsearch(x, l)
t2 = time.time()
T1 = t2-t1
print "Non-recursive binary search took",T1,"sec"

t1 = time.time()
recbinsearch(x, l)
t2 = time.time()
T2 = t2-t1
print "Recursive binary search took",T2,"sec"

print "Recursive is",T2/T1,"times slower than non-recursive"

def mergesort(L):
    """Ταξινομεί την L σε αύξουσα σειρά"""
    print "mergesort({L})".format(L=L) # Τυπώνουμε ποια λίστα ταξινομούμε
    
    N = len(L) # μήκος της λίστας
    m = N/2 # μέσο της λίστας
    
    # Αν η λίστα έχει μήκος 0, 1, 2 το κάνουμε με απλό τρόπο
    if N == 0:
        return L
    if N == 1:
        return L
    if N == 2:
        return [min(L), max(L)]
    
    # Αλλιώς ταξινομούμε το αριστερό και το δεξί μισό, αναδρομικά καλώντας τον εαυτό μας
    l = mergesort(L[:m])
    r = mergesort(L[m:])
    
    ll = [] # αυτή θα είναι η τελική λίστα, αρχικά κενή, που τη γεμίζουμε από τα δεξιά
    hl = 0 # πρώτο στοιχείο της αριστερής λίστας που δεν έχουμε χρησιμοποιήσει ακόμη
    hr = 0 # πρώτο στοιχείο της δεξιάς λίστας που δεν έχουμε χρησιμοποιήσει ακόμη
    
    for i in range(N):
        if hl >= len(l): # Αν έχει τελειώσει η αριστερή λίστα πάρε το στοιχείο από τη δεξιά
            z = r[hr]
            hr += 1
            ll.append(z)
            continue
        if hr >= len(r): # Αν έχει τελειώσει η δεξιά λίστα πάρε το στοιχείο από την αριστερή
            z = l[hl]
            hl += 1
            ll.append(z)
            continue
        if l[hl] < r[hr]: # Αν το πρώτο στοιχείο της αριστερής λίστας είναι το μικρότερο τότε πάρε αυτό
            z = l[hl]
            hl += 1
        else: # Αν το πρώτο στοιχείο της δεξιάς λίστας είναι το μικρότερο τότε πάρε αυτό
            z = r[hr]
            hr += 1
        ll.append(z)
    return ll

# Δοκιμάζουμε τη συνάρτηση εδώ
# Έχουμε βάλει τη συνάρτηση να τυπώνει το πότε ξεκινά να ταξινομεί μια λίστα ώστε να φαίνονται οι αναδρομικές κλήσεις
L = [1, 2, 4, 3, 10, 6, 5, 1, 2, 0, 11]
mergesort(L)