Find longest ascending series (not same as upsequence problem)

Given a sequence of distinct integers, remove as few elements as possible so that the remaining sequence appears sorted in ascending order.

Example:

1 2 3 8 10 5 6 7 12 9 11 4 0
1 2 3      5 6 7    9 11

Brute force solution:

def arrangements(k,arr):
        if len(arr) == 1:
                return [arr]
        if k == 1:
                return [ [i] for i in arr ]
        else:
                L=[]
                for i in arr:
                        iarr = arr[:]
                        iarr.remove(i)
                        for v in arrangement (k-1,iarr):
                                L.append ( [i] + v )
                return L

def is_ascending(arr):
        res = True
        for i in range(0,len(arr)-1):
                if arr[i] > arr[i+1]:
                        res = False
                        break
        return res

def longest_ascending(arr):
        max_arg = None
        max_size = 0
        for k in range (1,len(arr)):
                argts = arrangements (k,arr)
                for a in argts:
                        if is_ascending(a) and len(a) > max_size:
                                max_size = len(a)
                                max_arg = a

        return max_arg

Number of zeroes in factorial of a number

Write a function that returns the number of zeros contained in the factorial of the number that is passed to it.

Ok, so the easy solution is to calculate factorial and then count the nb of zeroes. But we cannot have very large number.
Our solution is to divide the number as we compute it by ten when it's possible and increment the counter:

count = 0
def zeroes(n):
        global count
        if n == 1:
                return 1
        else:
                v = n * zeroes(n-1)
                if v % 10 == 0:
                        print v
                        v /= 10
                        count += 1
                return v

print zeroes (100)
print count

import math
print math.factorial(100)

Printing all possible combinations of brackets

Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be

((())) (()()) (())() ()(()) ()()()

def brackets(n):
        if n == 2:
                return ["()"]
        else:
                L = []
                for b in brackets(n-2):
                        L.append( "(" + b + ")" )
                        L.append( "()" + b )
                        if not b.find ( "((" ):
                                L.append( b + "()" )
                return L

print brackets(2)
print brackets(6)

Print all possible variations of a password

An iterative version that has been implemented and tested:

def variations(str, char_variations):
        result = []
        for i in range(0,len(str)):
                tmp_result = []
                c = str[i]
                vars = char_variations.get(c)
                if vars is None:
                        vars = []
                vars = vars + [c]

                if len(result) > 0:
                        for partial_r in result:
                                for v in vars:
                                        tmp_result.append(partial_r + v)
                else:
                        for v in vars:
                                tmp_result.append(v)

                result = tmp_result

        return result


char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print variations ('allo' , char_variations)

An here is a recursive version that has been implemented and tested

def variations(str,char_variations):
        if len(str) == 0:
                return []

        c = str[0]
        vars = char_variations.get(c)

        if len(str) == 1:
             if vars:
                  return vars
             else:
                  return [c]

        if vars is None:
                vars = []
        vars = vars + [c]
        

        subL = variations (str, char_variations)
        L = []

        for l in subL:
                 for v in vars:
                        L += [ v + l ]
        
        return L

char_variations = { 'a': ['0','o'] , 'l': ['1' , 'I'] }

print map ( str , variations (list ('allo') , char_variations) )

Binary search and array rotation

The following solution has been implemented and verified:

def binsearch(arr, val, start, end):
    if start == end and arr[start] <> val:
       return -1
    index = (end+start)/2
    if val == arr[index]:
       return index
    elif val < arr[index]:
       return binsearch(arr, val, start , index)
    elif val > arr[index]:
       return binsearch(arr, val, index , end)

arr = range(1,8)
print arr
print binsearch ( arr , 3, 0, len(arr) )
print binsearch ( arr , 7, 0, len(arr) )

Additionnal question:
The array was rotated. How would search in it?

Answer, find the index of max value, iMax and in the previous function, replace

    index = (end+start)/2

by

    index = (iMax + (end+start)/2) % len(arr)

Print out all combinations of k numbers out of 1...N

e.g. when k = 2, n = 4
Print out 12, 13, 14, 23, 24, 34

def combi (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        for i in range (0,len(arr)):
                arr2 = arr[:]
                arr2.remove(arr[i])
                for v in  combi (k-1 , arr2):
                        L.append( [arr[i]] + v )

        return L

print combi ( 2 , range(1,4) ) 
 

One limitation with this function is that it returns 14 but also 41
The following code solves this problem

def combi2 (k,arr):
        if k == 1:
                return [[i] for i in arr]
        elif k == 0 or len(arr) == 0:
                return []

        L = []
        arr2 = arr[:]
        while len(arr2) > 0:
                val = arr2.pop(0)

                for v in  combi (k-1 , arr2):
                        L.append( [val] + v )

        return L