4. Arrays

#-----------------------------
# Python does not automatically flatten lists, in other words
# in the following, non-nested contains four elements and
# nested contains three elements, the third element of which
# is itself a list containing two elements:
non_nested = ["this", "that", "the", "other"]
nested = ["this", "that", ["the", "other"]]
#-----------------------------
tune = ["The", "Star-Spangled", "Banner"]
#-----------------------------

#-----------------------------
a = ["quick", "brown", "fox"]
a = "Why are you teasing me?".split()

text = """
    The boy stood on the burning deck,
    It was as hot as glass.
"""
lines = [line.lstrip() for line in text.strip().split("\n")]
#-----------------------------
biglist = [line.rstrip() for line in open("mydatafile")]
#-----------------------------
banner = "The Mines of Moria"
banner = 'The Mines of Moria'
#-----------------------------
name = "Gandalf"
banner = "Speak, " + name + ", and enter!"
banner = "Speak, %s, and welcome!" % name
#-----------------------------
his_host = "www.python.org"
import os
host_info = os.popen("nslookup " + his_host).read()

# NOTE: not really relevant to Python (no magic '$$' variable)
python_info = os.popen("ps %d" % os.getpid()).read()
shell_info = os.popen("ps $$").read()
#-----------------------------
# NOTE: not really relevant to Python (no automatic interpolation)
banner = ["Costs", "only", "$4.95"]
banner = "Costs only $4.95".split()
#-----------------------------
brax = """ ' " ( ) < > { } [ ] """.split()            #"""
brax = list("""'"()<>{}[]""")                         #"""
rings = '''They're  "Nenya Narya Vilya"'''.split()    #'''
tags   = 'LI TABLE TR TD A IMG H1 P'.split()
sample = r'The backslash (\) is often used in regular expressions.'.split()

#-----------------------------
banner = "The backslash (\\) is often used in regular expressions.".split()
#-----------------------------
ships = u"Niña Pinta Santa María".split()          # WRONG (only three ships)
ships = [u"Niña", u"Pinta", u"Santa María"]        # right
#-----------------------------

#-----------------------------
def commify_series(args):
    n = len(args)
    if n == 0: 
        return ""
    elif n == 1: 
        return args[0]
    elif n == 2: 
        return args[0] + " and " + args[1]
    return ", ".join(args[:-1]) + ", and " + args[-1]

commify_series([])
commify_series(["red"])
commify_series(["red", "yellow"])
commify_series(["red", "yellow", "green"])
#-----------------------------
mylist = ["red", "yellow", "green"]
print "I have", mylist, "marbles."
print "I have", " ".join(mylist), "marbles."
#=> I have ['red', 'yellow', 'green'] marbles.
#=> I have red yellow green marbles.

#-----------------------------
#!/usr/bin/env python
# commify_series - show proper comma insertion in list output
data = (
    ( 'just one thing', ),
    ( 'Mutt Jeff'.split() ),
    ( 'Peter Paul Mary'.split() ),
    ( 'To our parents', 'Mother Theresa', 'God' ),
    ( 'pastrami', 'ham and cheese', 'peanut butter and jelly', 'tuna' ),
    ( 'recycle tired, old phrases', 'ponder big, happy thoughts' ),
    ( 'recycle tired, old phrases',
      'ponder big, happy thoughts',
      'sleep and dream peacefully' ),
    )

def commify_series(terms):
    for term in terms:
        if "," in term:
            sepchar = "; "
            break
    else:
        sepchar = ", "

    n = len(terms)
    if n == 0: 
        return ""
    elif n == 1:
        return terms[0]
    elif n == 2:
        return " and ".join(terms)
    return "%s%sand %s" % (sepchar.join(terms[:-1]), sepchar, terms[-1])

for item in data:
    print "The list is: %s." % commify_series(item)

#=> The list is: just one thing.
#=> The list is: Mutt and Jeff.
#=> The list is: Peter, Paul, and Mary.
#=> The list is: To our parents, Mother Theresa, and God.
#=> The list is: pastrami, ham and cheese, peanut butter and jelly, and tuna.
#=> The list is: recycle tired, old phrases and ponder big, happy thoughts.
#=> The list is: recycle tired, old phrases; ponder big, happy thoughts; and
#   sleep and dream peacefully.
#-----------------------------

#-----------------------------
# Python allocates more space than is necessary every time a list needs to
# grow and only shrinks lists when more than half the available space is
# unused.  This means that adding or removing an element will in most cases
# not force a reallocation.

del mylist[size:]         # shrink mylist
mylist += [None] * size   # grow mylist by appending 'size' None elements

# To add an element to the end of a list, use the append method:
mylist.append(4)

# To insert an element, use the insert method:
mylist.insert(0, 10) # Insert 10 at the beginning of the list

# To extend one list with the contents of another, use the extend method:
list2 = [1,2,3]
mylist.extend(list2)

# To insert the contents of one list into another, overwriting zero or 
# more elements, specify a slice:
mylist[1:1] = list2   # Don't overwrite anything; grow mylist if needed
mylist[2:3] = list2   # Overwrite mylist[2] and grow mylist if needed

# To remove one element from the middle of a list:
# To remove elements from the middle of a list:
del mylist[idx1:idx2]  # 0 or more
x = mylist.pop(idx)    # remove mylist[idx] and assign it to x

# You cannot assign to or get a non-existent element:
# >>> x = []
# >>> x[4] = 5
#
# Traceback (most recent call last):
#   File "<pyshell#1>", line 1, in -toplevel-
#     x[4] = 5
# IndexError: list assignment index out of range
#
# >>> print x[1000]
#
# Traceback (most recent call last):
#  File "<pyshell#16>", line 1, in -toplevel-
#    print x[1000]
# IndexError: list index out of range
#-----------------------------
def what_about_that_list(terms):
    print "The list now has", len(terms), "elements."
    print "The index of the last element is", len(terms)-1, "(or -1)."
    print "Element #3 is %s." % terms[3]

people = "Crosby Stills Nash Young".split()
what_about_that_list(people)
#-----------------------------
#=> The list now has 4 elements.
#=> The index of the last element is 3 (or -1).
#=> Element #3 is Young.
#-----------------------------
people.pop()
what_about_that_list(people)
#-----------------------------
people += [None] * (10000 - len(people))
#-----------------------------
#>>> people += [None] * (10000 - len(people))
#>>> what_about_that_list(people)
#The list now has 10000 elements.
#The index of the last element is 9999 (or -1).
#Element #3 is None.
#-----------------------------

#-----------------------------
for item in mylist:
    pass # do something with item
#-----------------------------
for user in bad_users:
    complain(user)
#-----------------------------
import os
for (key, val) in sorted(os.environ.items()):
    print "%s=%s" % (key, val)
#-----------------------------
for user in all_users:
    disk_space = get_usage(user)    # find out how much disk space in use
    if disk_space > MAX_QUOTA:      # if it's more than we want ...
        complain(user)              # ... then object vociferously
#-----------------------------
import os
for line in os.popen("who"):
    if "dalke" in line:
        print line,  # or print line[:-1]

# or:
print "".join([line for line in os.popen("who")
                   if "dalke" in line]),

#-----------------------------
for line in myfile:
    for word in line.split(): # Split on whitespace
        print word[::-1],     # reverse word
    print

# pre 2.3:
for line in myfile:
    for word in line.split(): # Split on whitespace
        chars = list(word)    # Turn the string into a list of characters
        chars.reverse()
        print "".join(chars),
    print
#-----------------------------
for item in mylist:
    print "i =", item
#-----------------------------
# NOTE: you can't modify in place the way Perl does:
# data = [1, 2, 3]
# for elem in data:
#     elem -= 1
#print data
#=>[1, 2, 3]

data = [1, 2, 3]
data = [i-1 for i in data]
print data
#=>[0, 1, 2]

# or
for i, elem in enumerate(data):
    data[i] = elem - 1
#-----------------------------
# NOTE: strings are immutable in Python so this doesn't translate well.
s = s.strip()
data = [s.strip() for s in data]
for k, v in mydict.items():
    mydict[k] = v.strip()
#-----------------------------

#-----------------------------
fruits = ["Apple", "Blackberry"]
for fruit in fruits:
    print fruit, "tastes good in a pie."
#=> Apple tastes good in a pie.
#=> Blackberry tastes good in a pie.
#-----------------------------
# DON'T DO THIS:
for i in range(len(fruits)):
    print fruits[i], "tastes good in a pie."

# If you must explicitly index, use enumerate():
for i, fruit in enumerate(fruits):
    print "%s) %s tastes good in a pie."%(i+1, fruit)
#-----------------------------
rogue_cats = ["Morris", "Felix"]
namedict = { "felines": rogue_cats }
for cat in namedict["felines"]:
    print cat, "purrs hypnotically."
print "--More--\nYou are controlled."
#-----------------------------
# As noted before, if you need an index, use enumerate() and not this:
for i in range(len(namedict["felines"])):
    print namedict["felines"][i], "purrs hypnotically."
#-----------------------------

#-----------------------------
uniq = list(set(mylist))
#-----------------------------
# See http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/259174
# for a more heavyweight version of a bag
seen = {}
for item in mylist:
    seen[item] = seen.get(item, 0) + 1

uniq = seen.keys()
#-----------------------------
seen = {}
uniq = []
for item in mylist:
    count = seen.get(item, 0)
    if count == 0:
        uniq.append(item)
    seen[item] = count + 1
#-----------------------------
# generate a list of users logged in, removing duplicates
import os
usernames = [line.split()[0] for line in os.popen("who")]
uniq = sorted(set(usernames))
print "users logged in:", " ".join(uniq)

# DON'T DO THIS:
import os
ucnt = {}
for line in os.popen("who"):
    username = line.split()[0]  # Get the first word
    ucnt[username] = ucnt.get(username, 0) + 1 # record the users' presence

# extract and print unique keys
users = ucnt.keys()
users.sort()
print "users logged in:", " ".join(users)
#-----------------------------

#-----------------------------
# assume a_list and b_list are already loaded
aonly = [item for item in a_list if item not in b_list]

# A slightly more complex Pythonic version using sets - if you had a few
# lists, subtracting sets would be clearer than the listcomp version above
a_set = set(a_list)
b_set = set(b_list)
aonly = list(a_set - b_set)  # Elements in a_set but not in b_set

# DON'T DO THIS.
seen = {}                 # lookup table to test membership of B
aonly = []                # answer

#    build lookup table
for item in b_list:
    seen[item] = 1

#    find only elements in a_list and not in b_list
for item in a_list:
    if not item not in seen:
        # it's not in 'seen', so add to 'aonly'
        aonly.append(item)
#-----------------------------
# DON'T DO THIS.  There's lots of ways not to do it.
seen = {}   # lookup table
aonly = []  # answer

#     build lookup table - unnecessary and poor Python style
[seen.update({x: 1}) for x in b_list]

aonly = [item for item in a_list if item not in seen]

#-----------------------------
aonly = list(set(a_list))

# DON'T DO THIS.
seen = {}
aonly = []
for item in a_list:
    if item not in seen:
        aonly.append(item)
    seen[item] = 1                    # mark as seen
#-----------------------------
mydict["key1"] = 1
mydict["key2"] = 2
#-----------------------------
mydict[("key1", "key2")] = (1,2)
#-----------------------------
# DON'T DO THIS:
seen = dict.fromkeys(B.keys())

# DON'T DO THIS pre-2.3:
seen = {}
for term in B:
    seen[term] = None
#-----------------------------
# DON'T DO THIS:
seen = {}
for k, v in B:
    seen[k] = 1
#-----------------------------

#-----------------------------
a = (1, 3, 5, 6, 7, 8)
b = (2, 3, 5, 7, 9)

a_set = set(a)
b_set = set(b)

union = a_set | b_set   # or a_set.union(b_set)
isect = a_set & b_set   # or a_set.intersection(b_set) 
diff = a_set ^ b_set    # or a_set.symmetric_difference(b_set)


# DON'T DO THIS:
union_list = []; isect_list = []; diff = []
union_dict = {}; isect_dict = {}
count = {}
#-----------------------------
# DON'T DO THIS:
for e in a:
    union_dict[e] = 1

for e in b:
    if union_dict.has_key(e):
        isect_dict[e] = 1
    union_dict[e] = 1

union_list = union_dict.keys()
isect_list = isect_dict.keys()
#-----------------------------
# DON'T DO THIS:
for e in a + b:
    if union.get(e, 0) == 0:
        isect[e] = 1
    union[e] = 1

union = union.keys()
isect = isect.keys()
#-----------------------------
# DON'T DO THIS:
count = {}
for e in a + b:
    count[e] = count.get(e, 0) + 1

union = []; isect = []; diff = []

for e in count.keys():
    union.append(e)
    if count[e] == 2:
        isect.append(e)
    else:
        diff.append(e)
#-----------------------------
# DON'T DO THIS:
isect = []; diff = []; union = []
count = {}
for e in a + b:
    count[e] = count.get(e, 0) + 1

for e, num in count.items():
    union.append(e)
    [None, diff, isect][num].append(e)
#-----------------------------

#-----------------------------
# "append" for a single term and
# "extend" for many terms
mylist1.extend(mylist2)
#-----------------------------
mylist1 = mylist1 + mylist2
mylist1 += mylist2
#-----------------------------
members = ["Time", "Flies"]
initiates = ["An", "Arrow"]
members.extend(initiates)
# members is now ["Time", "Flies", "An", "Arrow"]
#-----------------------------
members[2:] = ["Like"] + initiates
print " ".join(members)
members[:1] = ["Fruit"]           # or members[1] = "Fruit"
members[-2:] = ["A", "Banana"]
print " ".join(members)
#-----------------------------
#=> Time Flies Like An Arrow
#=> Fruit Flies Like A Banana
#-----------------------------

#-----------------------------
# reverse mylist into revlist

revlist = mylist[::-1]

# or
revlist = list(reversed(mylist))

# or pre-2.3
revlist = mylist[:]    # shallow copy
revlist.reverse()
#-----------------------------
for elem in reversed(mylist):
    pass # do something with elem

# or
for elem in mylist[::-1]:
    pass # do something with elem

# if you need the index and the list won't take too much memory:
for i, elem in reversed(list(enumerate(mylist))):
    pass

# If you absolutely must explicitly index:
for i in range(len(mylist)-1, -1, -1):
    pass
#-----------------------------
descending = sorted(users, reverse=True)
#-----------------------------

#-----------------------------
# remove n elements from the front of mylist
mylist[:n] = []       # or del mylist[:n]

# remove n elements from front of mylist, saving them into front
front, mylist[:n] = mylist[:n], []

# remove 1 element from the front of mylist, saving it in front:
front = mylist.pop(0)

# remove n elements from the end of mylist
mylist[-n:] = []      # or del mylist[-n:]

# remove n elements from the end of mylist, saving them in end
end, mylist[-n:] = mylist[-n:], []

# remove 1 element from the end of mylist, saving it in end:
end = mylist.pop()

#-----------------------------
def shift2(terms):
    front = terms[:2]
    terms[:2] = []
    return front

def pop2(terms):
    back = terms[-2:]
    terms[-2:] = []
    return back
#-----------------------------
friends = "Peter Paul Mary Jim Tim".split()
this, that = shift2(friends)
# 'this' contains Peter, 'that' has Paul, and
# 'friends' has Mary, Jim, and Tim

beverages = "Dew Jolt Cola Sprite Fresca".split()
pair = pop2(beverages)
# pair[0] contains Sprite, pair[1] has Fresca,
# and 'beverages' has (Dew, Jolt, Cola)

# In general you probably shouldn't do things that way because it's 
# not clear from these calls that the lists are modified.
#-----------------------------

for item in mylist:
    if criterion:
        pass    # do something with matched item
        break
else:
    pass     # unfound
#-----------------------------
for idx, elem in enumerate(mylist):
    if criterion:
        pass    # do something with elem found at mylist[idx]
        break
else:
    pass ## unfound
#-----------------------------
# Assuming employees are sorted high->low by wage.
for employee in employees:
    if employee.category == 'engineer':
        highest_engineer = employee
        break

print "Highest paid engineer is:", highest_engineer.name
#-----------------------------
# If you need the index, use enumerate:
for i, employee in enumerate(employees):
    if employee.category == 'engineer':
        highest_engineer = employee
        break
print "Highest paid engineer is: #%s - %s" % (i, highest_engineer.name)


# The following is rarely appropriate:
for i in range(len(mylist)):
    if criterion:
        pass    # do something
        break
else:
    pass ## not found
#-----------------------------

matching = [term for term in mylist if test(term)]
#-----------------------------
matching = []
for term in mylist:
    if test(term):
        matching.append(term)
#-----------------------------
bigs = [num for num in nums if num > 1000000]
pigs = [user for (user, val) in users.items() if val > 1e7]
#-----------------------------
import os
matching = [line for line in os.popen("who") 
                if line.startswith("gnat ")]
#-----------------------------
engineers = [employee for employee in employees
                 if employee.position == "Engineer"]
#-----------------------------
secondary_assistance = [applicant for applicant in applicants
                            if 26000 <= applicant.income < 30000]
#-----------------------------

sorted_list = sorted(unsorted_list)
#-----------------------------
# pids is an unsorted list of process IDs
import os, signal, time
for pid in sorted(pids):
    print pid

pid = raw_input("Select a process ID to kill: ")
try:
    pid = int(pid)
except ValueError:
    raise SystemExit("Exiting ... ")
os.kill(pid, signal.SIGTERM)
time.sleep(2)
try:
    os.kill(pid, signal.SIGKILL)
except OSError, err:
    if err.errno != 3:  # was it already killed?
        raise
#-----------------------------
descending = sorted(unsorted_list, reverse=True)
#-----------------------------
allnums = [4, 19, 8, 3]
allnums.sort(reverse=True)              # inplace
#-----------------------------
# pre 2.3
allnums.sort()                          # inplace
allnums.reverse()                       # inplace
#or
allnums = sorted(allnums, reverse=True) # reallocating
#-----------------------------

ordered = sorted(unordered, cmp=compare)
#-----------------------------
ordered = sorted(unordered, key=compute)

# ...which is somewhat equivalent to: 
precomputed = [(compute(x), x) for x in unordered]
precomputed.sort(lambda a, b: cmp(a[0], b[0]))
ordered = [v for k,v in precomputed.items()]
#-----------------------------
# DON'T DO THIS.
def functional_sort(mylist, function):
    mylist.sort(function)
    return mylist

ordered = [v for k,v in functional_sort([(compute(x), x) for x in unordered],
                                        lambda a, b: cmp(a[0], b[0]))]
#-----------------------------
ordered = sorted(employees, key=lambda x: x.name)
#-----------------------------
for employee in sorted(employees, key=lambda x: x.name):
    print "%s earns $%s" % (employee.name, employee.salary)
#-----------------------------
sorted_employees = sorted(employees, key=lambda x: x.name):
for employee in sorted_employees:
    print "%s earns $%s" % (employee.name, employee.salary)

# load bonus
for employee in sorted_employees:
    if bonus(employee.ssn):
        print employee.name, "got a bonus!"
#-----------------------------
sorted_employees = sorted(employees, key=lambda x: (x.name, x.age)):
#-----------------------------
# NOTE: Python should allow access to the pwd fields by name
# as well as by position.
import pwd
# fetch all users
users = pwd.getpwall()
for user in sorted(users, key=lambda x: x[0]):
    print user[0]
#-----------------------------
sorted_list = sorted(names, key=lambda x: x[:1])
#-----------------------------
sorted_list = sorted(strings, key=len)
#-----------------------------
# DON'T DO THIS.
temp = [(len(s), s) for s in strings]
temp.sort(lambda a, b: cmp(a[0], b[0]))
sorted_list = [x[1] for x in temp]
#-----------------------------
# DON'T DO THIS.
def functional_sort(mylist, function):
    mylist.sort(function)
    return mylist

sorted_fields = [v for k,v in functional_sort(
              [(int(re.search(r"(\d+)", x).group(1)), x) for x in fields],
                                   lambda a, b: cmp(a[0], b[0]))]
#-----------------------------
entries = [line[:-1].split() for line in open("/etc/passwd")]

for entry in sorted(entries, key=lambda x: (x[3], x[2], x[0])):
    print entry
#-----------------------------

#-----------------------------
import itertools
for process in itertools.cycle([1, 2, 3, 4, 5]):
    print "Handling process", process
    time.sleep(1)

# pre 2.3:
import time
class Circular(object):
    def __init__(self, data):
        assert len(data) >= 1, "Cannot use an empty list"
        self.data = data

    def __iter__(self):
        while True:
            for elem in self.data:
                yield elem

circular = Circular([1, 2, 3, 4, 5])

for process in circular:
    print "Handling process", process
    time.sleep(1)

# DON'T DO THIS. All those pops and appends mean that the list needs to be 
# constantly reallocated.  This is rather bad if your list is large:
import time
class Circular(object):
    def __init__(self, data):
        assert len(data) >= 1, "Cannot use an empty list"
        self.data = data

    def next(self):
        head = self.data.pop(0)
        self.data.append(head)
        return head

circular = Circular([1, 2, 3, 4, 5])
while True:
    process = circular.next()
    print "Handling process", process
    time.sleep(1)
#-----------------------------

#-----------------------------
# generate a random permutation of mylist in place
import random
random.shuffle(mylist)
#-----------------------------

#-----------------------------
import sys

def make_columns(mylist, screen_width=78):
    if mylist:
        maxlen = max([len(elem) for elem in mylist])
        maxlen += 1   # to make extra space

        cols = max(1, screen_width/maxlen) 
        rows = 1 + len(mylist)/cols

        # pre-create mask for faster computation
        mask = "%%-%ds " % (maxlen-1)

        for n in range(rows):
            row = [mask%elem
                       for elem in mylist[n::rows]]
            yield "".join(row).rstrip()

for row in make_columns(sys.stdin.readlines(), screen_width=50):
    print row


# A more literal translation
import sys

# subroutine to check whether at last item on line
def EOL(item):
    return (item+1) % cols == 0

# Might not be portable to non-linux systems
def getwinsize():
    # Use the curses module if installed
    try:
        import curses
        stdscr = curses.initscr()
        rows, cols = stdscr.getmaxyx()
        return cols
    except ImportError:
        pass

    # Nope, so deal with ioctl directly.  What value for TIOCGWINSZ?
    try:
        import termios
        TIOCGWINSZ = termios.TIOCGWINSZ
    except ImportError:
        TIOCGWINSZ = 0x40087468  # This is Linux specific

    import struct, fcntl
    s = struct.pack("HHHH", 0, 0, 0, 0)
    try:
        x = fcntl.ioctl(sys.stdout.fileno(), TIOCGWINSZ, s)
    except IOError:
        return 80
    rows, cols = struct.unpack("HHHH", x)[:2]
    return cols

cols = getwinsize()

data = [s.rstrip() for s in sys.stdin.readlines()]
if not data:
    maxlen = 1
else:
    maxlen = max(map(len, data))

maxlen += 1       # to make extra space

# determine boundaries of screen
cols = (cols / maxlen) or 1
rows = (len(data)+cols) / cols

# pre-create mask for faster computation
mask = "%%-%ds " % (maxlen-1)

# now process each item, picking out proper piece for this position
for item in range(rows * cols):
    target = (item % cols) * rows + (item/cols)
    if target < len(data):
        piece = mask % data[target]
    else:
        piece = mask % ""
    if EOL(item):
        piece = piece.rstrip()  # don't blank-pad to EOL
    sys.stdout.write(piece)
    if EOL(item):
        sys.stdout.write("\n")

if EOL(item):
  sys.stdout.write("\n")
#-----------------------------

#-----------------------------
def factorial(n):
    s = 1
    while n:
        s *= n
        n -= 1
    return s   
#-----------------------------
def permute(alist, blist=[]):
    if not alist:
        yield blist
    for i, elem in enumerate(alist):
        for elem in permute(alist[:i] + alist[i+1:], blist + [elem]):
            yield elem

for permutation in permute(range(4)):
    print permutation
#-----------------------------
# DON'T DO THIS
import fileinput

# Slightly modified from
#   http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463
def print_list(alist, blist=[]):
    if not alist:
        print ' '.join(blist)
    for i in range(len(alist)):
        blist.append(alist.pop(i))
        print_list(alist, blist)
        alist.insert(i, blist.pop())

for line in fileinput.input():
    words = line.split()
    print_list(words)
#-----------------------------
class FactorialMemo(list):
    def __init__(self):
        self.append(1)
        
    def __call__(self, n):
        try:
            return self[n]
        except IndexError:
            ret = n * self(n-1)
            self.append(ret)
            return ret

factorial = FactorialMemo()

import sys
import time
sys.setrecursionlimit(10000)

start = time.time()
factorial(2000)
f1 = time.time() - start
factorial(2100)                 # First 2000 values are cached already
f2 = time.time() - f1 - start
print "Slow first time:", f1
print "Quicker the second time:", f2
#-----------------------------

class MemoizedPermutations(list):
    def __init__(self, alist):
        self.permute(alist, [])
        
    def permute(self, alist, blist):
        if not alist:
            self.append(blist)
        for i, elem in enumerate(alist):
            self.permute(alist[:i] + alist[i+1:], blist + [elem])

    def __call__(self, seq, idx):
        return [seq[n] for n in self[idx]]


p5 = MemoizedPermutations(range(5))

words = "This sentence has five words".split()
print p5(words, 17)
print p5(words, 81)
#-----------------------------