UNIT-5

Iterators in Python

Iterator in python is any python type that can be used with a ‘for in loop’. Python lists,
tuples, dicts and sets are all examples of inbuilt iterators. These types are iterators
because they implement following methods. In fact, any object that wants to be an
iterator must implement following methods.
1. __iter__ method that is called on initialization of an iterator. This should return
an object that has a next or __next__ (in Python 3) method.

2. next ( __next__ in Python 3) The iterator next method should return the next
value for the iterable. When an iterator is used with a ‘for in’ loop, the for loop
implicitly calls next() on the iterator object. This method should raise a
StopIteration to signal the end of the iteration.

Below is a simple Python program that creates iterator type that iterates from 10 to
given limit. For example, if limit is 15, then it prints 10 11 12 13 14 15. And if limit is 5,
then it prints nothing.
# A simple Python program to demonstrate
# working of iterators using an example type
# that iterates from 10 to given value

# An iterable user defined type

class Test:

# Constructor
def __init__(self, limit):
self.limit = limit

# Called when iteration is initialized

def __iter__(self):
self.x = 10
return self

# To move to next element. In Python 3,

# we should replace next with __next__
def next(self):

# Store current value ofx

x = self.x

# Stop iteration if limit is reached

if x > self.limit:
raise StopIteration

# Else increment and return old value

self.x = x + 1;
return x

119 | P a g e Python Programming (KNC-302)

# Prints numbers from 10 to 15
for i in Test(15):
print(i)

# Prints nothing
for i in Test(5):
print(i)

Output :
10
11
12
13
14
15

Python Recursive Function

We know that in Python, a function can call other functions. It is even possible for
the function to call itself. These type of construct are termed as recursive
functions.

Following is an example of recursive function to find the factorial of an integer.

Factorial of a number is the product of all the integers from 1 to that number. For
example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.

Example of recursive function

# An example of a recursive function to

# find the factorial of a number

def calc_factorial(x):
"""This is a recursive function
to find the factorial of an integer"""

if x == 1:
return 1
else:
return (x * calc_factorial(x-1))

num = 4
print("The factorial of", num, "is", calc_factorial(num))

In the above example, calc_factorial() is a recursive functions as it calls itself.

120 | P a g e Python Programming (KNC-302)

 When we call this function with a positive integer, it will recursively call itself by
decreasing the number.

Each function call multiples the number with the factorial of number 1 until the number
is equal to one.

#Recursive Python Program for Fibonacci Series:

1. def recur_fibo(n):
2. if n <= 1:
3. return n
4. else:
5. return(recur_fibo(n-1) + recur_fibo(n-2))
6. # take input from the user
7. nterms = int(input("How many terms? "))
8. # check if the number of terms is valid
9. if nterms <= 0:
10. print("Plese enter a positive integer")
11. else:
12. print("Fibonacci sequence:")
13. for i in range(nterms):
14. print(recur_fibo(i))

Python Program for Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The
objective of the puzzle is to move the entire stack to another rod, obeying the following
simple rules:

1) Only one disk can be moved at a time.

2) Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.

121 | P a g e Python Programming (KNC-302)

# Recursive Python function to solve tower of hanoi

def TowerOfHanoi(n , from_rod, to_rod, aux_rod):

if n == 1:

print "Move disk 1 from rod",from_rod,"to rod",to_rod

return

TowerOfHanoi(n-1, from_rod, aux_rod, to_rod)

print "Move disk",n,"from rod",from_rod,"to rod",to_rod

TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)

# Driver code

n=4

TowerOfHanoi(n, \'A\', \'C\', \'B\')

# A, C, B are the name of rods

Output:
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 3 from rod A to rod B
Move disk 1 from rod C to rod A
Move disk 2 from rod C to rod B
Move disk 1 from rod A to rod B
Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C
Move disk 2 from rod B to rod A
Move disk 1 from rod C to rod A
Move disk 3 from rod B to rod C
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C

122 | P a g e Python Programming (KNC-302)

 Python Program to Implement Linear Search
This is a Python program to implement linear search.
Problem Description

The program takes a list and key as input and finds the index of the key in the list using
linear search.
Problem Solution

1. Create a function linear_search that takes a list and key as arguemnts.

2. A loop iterates through the list and when an item matching the key is found, the
corresponding index is returned.
3. If no such item is found, -1 is returned.
Program/Source Code

Here is the source code of a Python program to implement linear search. The program
output is shown below.
def linear_search(alist, key):
"""Return index of key in alist. Return -1 if key not present."""
for i in range(len(alist)):
if alist[i] == key:
return i
return -1

alist = input('Enter the list of numbers: ')

alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))

index = linear_search(alist, key)

if index < 0:
print('{} was not found.'.format(key))
else:
print('{} was found at index {}.'.format(key, index))

Program Explanation

1. The user is prompted to enter a list of numbers.

2. The user is then asked to enter a key to search for.
3. The list and key is passed to linear_search.

123 | P a g e Python Programming (KNC-302)

4. If the return value is -1, the key is not found and a message is displayed, otherwise
the index of the found item is displayed.
Runtime Test Cases

Case 1:
Enter the list of numbers: 5 4 3 2 1 10 11 2
The number to search for: 1
1 was found at index 4.

Case 2:
Enter the list of numbers: 5 2 1 5 -3
The number to search for: 2
2 was found at index 1.

Case 3:
Enter the list of numbers: 3 5 6
The number to search for: 2
2 was not found.

Python Program to Implement Binary Search

Problem Description

The program takes a list and key as input and finds the index of the key in the list using
binary search.
Problem Solution

1. Create a function binary_search that takes a list and key as arguments.

2. The variable start is set to 0 and end is set to the length of the list.
3. The variable start keeps track of the first element in the part of the list being
searched while end keeps track of the element one after the end of the part being
searched.
4. A while loop is created that iterates as long as start is less than end.
5. mid is calculated as the floor of the average of start and end.
6. If the element at index mid is less than key, start is set to mid + 1 and if it is more
than key, end is set to mid. Otherwise, mid is returned as the index of the found
element.
7. If no such item is found, -1 is returned.
Program/Source Code

Here is the source code of a Python program to implement binary search without using
recursion. The program output is shown below.
def binary_search(alist, key):
"""Search key in alist[start... end - 1]."""
start = 0
end = len(alist)
while start < end:
mid = (start + end)//2
if alist[mid] > key:
124 | P a g e Python Programming (KNC-302)
 end = mid
elif alist[mid] < key:
start = mid + 1
else:
return mid
return -1

alist = input('Enter the sorted list of numbers: ')

alist = alist.split()
alist = [int(x) for x in alist]
key = int(input('The number to search for: '))

index = binary_search(alist, key)

if index < 0:
print('{} was not found.'.format(key))
else:
print('{} was found at index {}.'.format(key, index))

Program Explanation

1. The user is prompted to enter a list of numbers.

2. The user is then asked to enter a key to search for.
3. The list and key is passed to binary_search.
4. If the return value is -1, the key is not found and a message is displayed, otherwise
the index of the found item is displayed.
Runtime Test Cases

Case 1:
Enter the sorted list of numbers: 3 5 10 12 15 20
The number to search for: 12
12 was found at index 3.

Case 2:
Enter the sorted list of numbers: -3 0 1 5 6 7 8
The number to search for: 2
2 was not found.

Case 3:
Enter the sorted list of numbers: 5
The number to search for: 5
5 was found at index 0.

125 | P a g e Python Programming (KNC-302)

 Python Program to Implement Selection Sort

This is a Python program to implement selection sort.

Problem Description

The program sorts a list by selection sort.

Problem Solution

1. Create a function selection_sort that takes a list as argument.

2. Inside the function create a loop with a loop variable i that counts from 0 to the
length of the list – 1.
3. Create a variable smallest with initial value i.
4. Create an inner loop with a loop variable j that counts from i + 1 up to the length of
the list – 1.
5. Inside the inner loop, if the elements at index j is smaller than the element at index
smallest, then set smallest equal to j.
6. After the inner loop finishes, swap the elements at indexes i and smallest.
Program/Source Code

Here is the source code of a Python program to implement selection sort. The program
output is shown below.
def selection_sort(alist):
for i in range(0, len(alist) - 1):
smallest = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[smallest]:
smallest = j
alist[i], alist[smallest] = alist[smallest], alist[i]

alist = input('Enter the list of numbers: ').split()

alist = [int(x) for x in alist]
selection_sort(alist)
print('Sorted list: ', end='')
print(alist)

Program Explanation

1. The user is prompted to enter a list of numbers.

2. The list is passed to the selection_sort function.
3. The sorted list is displayed.
Runtime Test Cases

Case 1:
Enter the list of numbers: 3 1 4 5 2 6

126 | P a g e Python Programming (KNC-302)

Sorted list: [1, 2, 3, 4, 5, 6]

Case 2:
Enter the list of numbers: 2 10 5 38 1 7
Sorted list: [1, 2, 5, 7, 10, 38]

Case 3:
Enter the list of numbers: 5 3 2 1 0
Sorted list: [0, 1, 2, 3, 5]

Python Program to Implement Merge Sort

This is a Python program to implement merge sort.

Problem Description

The program sorts a list by merge sort.

Problem Solution

1. Create a function merge_sort that takes a list and two variables start and end as
arguments.
2. The function merge_sort will sort the list from indexes start to end – 1 inclusive.
3. If end – start is not greater than 1, then return.
4. Otherwise, set mid equal to the floor of (start + end)/2.
5. Call merge_sort with the same list and with start = start and end = mid as
arguments.
6. Call merge_sort with the same list and with start = mid and end = end as
arguments.
7. Call the function merge_list, passing the list and the variables start, mid and end as
arguments.
8. The function merge_list takes a list and three numbers, start, mid and end as
arguments and assuming the list is sorted from indexes start to mid – 1 and from mid
to end – 1, merges them to create a new sorted list from indexes start to end – 1.
Program/Source Code

Here is the source code of a Python program to implement merge sort. The program
output is shown below.
def merge_sort(alist, start, end):
'''Sorts the list from indexes start to end - 1 inclusive.'''
if end - start > 1:
mid = (start + end)//2
merge_sort(alist, start, mid)
merge_sort(alist, mid, end)
merge_list(alist, start, mid, end)

def merge_list(alist, start, mid, end):

left = alist[start:mid]
right = alist[mid:end]
k = start
i = 0
j = 0
127 | P a g e Python Programming (KNC-302)
 while (start + i < mid and mid + j < end):
if (left[i] <= right[j]):
alist[k] = left[i]
i = i + 1
else:
alist[k] = right[j]
j = j + 1
k = k + 1
if start + i < mid:
while k < end:
alist[k] = left[i]
i = i + 1
k = k + 1
else:
while k < end:
alist[k] = right[j]
j = j + 1
k = k + 1

alist = input('Enter the list of numbers: ').split()

alist = [int(x) for x in alist]
merge_sort(alist, 0, len(alist))
print('Sorted list: ', end='')
print(alist)

Program Explanation

1. The user is prompted to enter a list of numbers.

2. The list is passed to the merge_sort function.
3. The sorted list is displayed.
Runtime Test Cases

Case 1:
Enter the list of numbers: 3 1 5 8 2 5 1 3
Sorted list: [1, 1, 2, 3, 3, 5, 5, 8]

Case 2:
Enter the list of numbers: 5 3 2 1 0
Sorted list: [0, 1, 2, 3, 5]

Case 3:
Enter the list of numbers: 1
Sorted list: [1]

128 | P a g e Python Programming (KNC-302)

 Higher order sort

sorted

sorted does pretty much the same thing what you expected.

# sorting numbers
In [0]: sorted([9, 5, 7])
Out[0]: [5, 7, 9]

# sorting alphabetically
In [0]: sorted(['foo', 'bar'])
Out[0]: ['bar', 'foo']

Using Key :key:

Well you can also customize the sorting also, the parameter key. The key needs to be
a simple function the takes a single value that tells python the value to use in sorting it.

In [0]: sorted([1, -3, 2]) # sorting normally

Out[0]: [-3, 1, 2]

In [0]: sorted([1, -2, 0], key=abs) # sorting by absolute values

Out[0]: [0, 1, -2]

Note: abs is the absolute value function. i.e. abs(-3) = 3

129 | P a g e Python Programming (KNC-302)