Shared2018-01-29-140733.ipynbOpen in CoCalc
# Fibonacci Series
def fib(n):
    a,b=0,1
    while(a<n):
        print(a,end=' ')
        a,b=b,a+b
fib(5)

0 1 1 2 3
#binary Search (Iterative)
import time
a=input().split(' ')
for i in range(len(a)):
    a[i]=int(a[i])
c=0
i=0
n=len(a)
x=int(input())
start=time.time()
while(i<n):
    mid=(i+n)//2
    if(a[mid]==int(x)):
        c+=1
        print("Element found at ", (mid+1))
        break
    elif(a[mid]>int(x)):
        c+=2
        n=mid-1
    else:
        c+=2
        i=mid+1    
end=time.time()
print("Element compared is ",c)
print("Time req is ", end-start)
Element found at 13 5 Time req is 0.005337953567504883
#Pattern Pyramid 
x=input()
x=int(x)
for i in range(x):
    
    for k in range(x-i):
        print("",end=" ")
    
    for j in range(i):
        print("*",end=" ")
    print()
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
def Ssort(a):
    for i in range(0,len(a)-1):
        j=i
        mini=j
        for j in range(j,len(a)):
            if(a[j]<a[mini]) :
                mini=j
        a[i],a[mini]=a[mini],a[i]
    print(a)
a=[5,4,3,2,1]
Ssort(a)
[1, 2, 3, 4, 5]
#insertion Sort
def Isort(a):
    for i in range(1,len(a)):
        j=i-1
        temp=a[i]
        while(a[j]>temp and j>=0):
            a[j+1]=a[j]
            j=j-1
        a[j+1]=temp
a=[5,4,3,2,1]
Isort(a)
print(a)        
    
[1, 2, 3, 4, 5]
#Binary Search (recursive)
def bin(a,x,l,r):
    mid=(l+r)//2
    if(a[mid]==x): print( mid+1)
    elif(a[mid]>x): bin(a,x,l,mid-1)
    else :
        bin(a,x,mid-1,r)
a=[1,2,3,4,5]
bin(a,3,0,4)

3
x=input()
x=int(x)
for i in range(x):
    
    for j in range(i):
        print("*",end=" ")
    print()
* * * * * * * * * *
#Factorial
import time
def fac(x):
    global c
    c+=1
    if(x==1): return 1
    else: return x*fac(x-1)
start=time.time()

c=0
print(fac(int(input())))  
end=time.time()
print("Camparison is ",c)
print("time is ",end-start)
120 Camparison is 5 time is 2.9848825931549072
#table generator 
def tab(n):
    for i in  range(1,11):
        print(n*i,end=" ")
tab(5)        
5 10 15 20 25 30 35 40 45 50
#Prime Number
def prime(x):
    for i in range(2,x-1):
        if(x%i==0):
            print("NOT PRIME")
            return
    print("IS PRIME")

prime(4)
            
NOT PRIME
#ODD EVEN
def even(x):
    if(x%2==0): print("EVEN")
    else : print("ODD")
even(97)        
ODD
#merge Sort
import random
import time
def merge(a,b):
    global co
    c = []
    while len(a) != 0 and len(b) != 0:
        co+=2
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    co+=2
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

def mergesort(x):
    global co
    co+=1
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = (len(x)//2)
        a = mergesort((x[:middle]))
        b = mergesort(x[middle:])
        return merge(a,b)
co=0    
start=time.time()
bb=random.sample(range(100),10)
print (bb)
bb=mergesort(bb)
end=time.time()
print(bb) 
print("Comparison is ",c)
print("Time is ",end-start)
[60, 64, 72, 35, 71, 97, 94, 49, 87, 3] [3, 35, 49, 60, 64, 71, 72, 87, 94, 97] Comparison is 121 Time is 0.0002970695495605469
#Quick sort
import random
import time
c=0
def quicksort(myList, start, end):
    global c
    if start < end:
        c+=1
        pivot = partition(myList, start, end)
        quicksort(myList, start, pivot-1)
        quicksort(myList, pivot+1, end)
    return myList
def partition(myList, start, end):
    global c
    pivot = myList[start]
    left = start+1
    right = end
    done = False
    while not done:
        c+=1
        while left <= right and myList[left] <= pivot:
            c+=1
            left = left + 1
        while myList[right] >= pivot and right >=left:
            c+=1
            right = right -1
        if right < left:
            c+=1
            done= True
        else:
            c+=1
            temp=myList[left]
            myList[left]=myList[right]
            myList[right]=temp
    temp=myList[start]
    myList[start]=myList[right]
    myList[right]=temp
    return right
start=time.time()
a=random.sample(range(50),20)
print(a)
a=quicksort(a,0,len(a)-1)
end=time.time()
print(a)
print("Camparisons are ",c)
print("Time is ",end-start)


[28, 0, 27, 17, 44, 15, 40, 25, 41, 16, 4, 31, 2, 12, 23, 7, 46, 33, 19, 5] [0, 2, 4, 5, 7, 12, 15, 16, 17, 19, 23, 25, 27, 28, 31, 33, 40, 41, 44, 46] Camparisons are 121 Time is 0.0024688243865966797
#Tower of Hannoi 
import time
co=0
def TOH(n,a,b,c):
    global co
    if n==1:
        co=co+1
        print("Disk",a,"Moved To ",c)
    else:
        TOH(n-1,a,c,b)
        TOH(1,a,b,c)
        TOH(n-1,b,a,c)

start=time.time()
a='A'
b='B'
c='C'
print("Enter The Number Of Disks")
n=int(input(""))
TOH(n,a,b,c)
end=time.time()
print("Time Taken To Execute ",end-start)
print("Number of comparisons is ",co)
Enter The Number Of Disks
Disk A Moved To C Disk A Moved To B Disk C Moved To B Disk A Moved To C Disk B Moved To A Disk B Moved To C Disk A Moved To C Time Taken To Execute 3.1265907287597656 Number of comparisons is 7
#MIXMAX Iterative
import time
import random
def  mixmax(a):
    l=len(a)
    min=a[0]
    max=a[0]
    for i in range(l):
        if(a[i]> max ): 
            max=a[i]
        elif(a[i]<min):
            min=a[i]
    print("Min and Max are ",min,max)
    return l*2   
a=[1,2,3,4,5]
start=time.time()
a=random.sample(range(100),20)
print(a)
c=mixmax(a)
end=time.time()
print("Camparisons are ",c)
print("Time is ",end-start)
    

[89, 48, 3, 84, 13, 1, 40, 14, 44, 4, 34, 87, 17, 22, 10, 12, 38, 78, 86, 74] Min and Max are 1 89 Camparisons are 40 Time is 0.004586935043334961

#Coin Selection dafault 
import random
import time
def coin(cost):
    a=[2000, 500, 200, 100, 50, 20, 10, 5, 2, 1]
    denom=[0,0,0,0,0,0,0,0,0,0]
    while ( cost>0 ):
        for i in range(len(a)):
            while(a[i]<=cost):
                denom[i]+=1
                cost-=a[i]
    for i in range(len(denom)):
        if denom[i]>0:
            print (denom[i]," Notes/Coins of Rs.",a[i])
coin(2541)

1 Notes/Coins of Rs. 2000 1 Notes/Coins of Rs. 500 2 Notes/Coins of Rs. 20 1 Notes/Coins of Rs. 1

#Binary Search tree
import random
class Node:
    def __init__(self,data):
        self.value=data
        self.leftchild=None
        self.rightchild=None 
    def insert(self,data):
        if(self.value == data):
            return False
        elif self.value>data:
                if self.leftchild:
                    return self.leftchild.insert(data)
                else :
                    self.leftchild=Node(data)
        else :
            if self.rightchild:
                return self.rightchild.insert(data)
            else: self.rightchild=Node(data)
    def find(self,data):
        if self.value==data:
            return True
        elif self.value>data:
            if self.leftchild:
                return self.leftchild.find(data)
            else :
                return Flase
        else :
            if self.rightchild:
                return self.rightchild.find(data)
            else : return False 
            
    def pre(self):
        if self: print(self.value,end=" ")
        if self.leftchild : self.leftchild.pre()
        if self.rightchild : self.rightchild.pre()

    def post(self):
        if self.leftchild: self.leftchild.post()
        if self.rightchild : self.rightchild.post()
        if self: print(self.value,end= " ")
            
    def ino(self):
         if self.leftchild : self.leftchild.ino()
         if self: print(self.value, end= " ")
         if self.rightchild :self.rightchild.ino()
        
class Tree:
    def __init__(self):
        self.root= None 
    def insert(self,data):
        if self.root:
            return self.root.insert(data)
        else :
            self.root=Node(data)
    def find(self,data):
        if self.root==None : return false
        else : return self.root.find(data)
    def pre(self):
        if self.root == None :
            return False
        else: self.root.pre()

    def post(self):
        if self.root == None :
            return False
        else: self.root.post()
    
    def ino(self):
        if self.root == None :
            return False
        else: self.root.ino()

bst=Tree()
bst.insert(12)
bst.insert(13)
bst.insert(11)
bst.insert(16)
bst.insert(18)
bst.insert(14)
bst.pre()
print()
bst.ino()
print()
bst.post()
12 11 13 16 14 18 11 12 13 14 16 18 11 14 18 16 13 12
#coin Select (user dependent )
a=input("The Currencies ").split(' ')
b=input("Denominations ").split(' ')
a=[int(x) for x in a]
b=[int(x) for x in b]
a=[[a[i],b[i],0] for i in range(len(a))]
a.sort(key=lambda x:x[0],reverse=True)
n=int(input("Enter the Amount "))
for i in range(len(a)):
    if sum([x[1] for x in a]) ==0:
        print("Not Enough Currency ")
        break;
        exit()
    while n!=0 and a[i][1]!=0 and a[i][0]<=n:
        a[i][1]-=1
        n-=a[i][0]
        a[i][2]+=1
if(n!=0):
    print("Not Enough Currency ")
    exit()
for x in a:
    if x[2]> 0:    print(x[2], " Notes/Coins of Rs.",x[0])
    

The Currencies
Denominations
#heap Sort 
def heapify(arr, n, i):
    largest = i  
    l = 2 * i + 1 
    r = 2 * i + 2 
 
    if l < n and arr[i] < arr[l]:
        largest = l
 
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i],arr[largest] = arr[largest],arr[i]  # swap
 
        heapify(arr, n, largest)
def heapSort(arr):
    n = len(arr)
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]   # swap
        heapify(arr, i, 0)
    return 
import random
import time
arr=random.sample(range(100),10)
print(arr)
start=time.time()
heapSort(arr)
end=time.time()
print (arr)
print("Time required is " ,end-start)
[74, 6, 55, 91, 98, 18, 9, 1, 41, 30] [1, 6, 9, 18, 30, 41, 55, 74, 91, 98] Time required is 0.00014543533325195312
# greedy knapsack(fractional) :-

from random import random
def built(n):
    l=[]
    for i in range (n):
        l.append((i,1+int(9*random()),1+int(9*random())))
    return l
r=built(5)
def weight(r):
     return r[1]
def profit(r):
     return r[2]
def density(r):
     return(r[2])/r[1]

def greedy_knapsack(r,m,k=None):
    knapsack=[]
    k.weight=0
    k.profit=0
    i=sorted(r,key=k)
    while(len(i)>0):
        j=i.pop()
        if(j[1]<=m):
            knapsack.append(j)
            k.weight+=j[1]
            k.profit+=j[2]
            m=m-j[1]
        else:
            knapsack.append(j)
            k.weight+=m
            k.profit+=(float(m)/j[1])*j[2]
            m=0
    return knapsack,k.weight,k.profit
a,b,c=greedy_knapsack(r,10,density)
print(a,"\n",b,"\n",c)

[(1, 3, 7), (0, 4, 8), (4, 7, 8), (3, 7, 6), (2, 7, 6)] 10 18.428571428571427
#Knapsack Dynamic
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
val = [51, 33, 44]
wt = [32, 24, 11]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
95
#Dynamic Fibonacci
def DF(n,table = []):
    while len(table) < n+1: table.append(0)
    if n <= 1:
        return n   

    else:
        if table[n-1] == 0:
            table[n-1] = DF(n-1)
        if table[n-2] == 0:
            table[n-2] = DF(n-2)
        table[n] = table[n-2] + table[n-1]
    return table[n]
DF(12)
144

#Longest Common Subsequence 
def lis(arr):
    n = len(arr)
    lis = [1]*n
    for i in range (1 , n):
        for j in range(0 , i):
            if arr[i] > arr[j] and lis[i]< lis[j] + 1 :
                lis[i] = lis[j]+1

    maximum = 0
    for i in range(n):
        maximum = max(maximum , lis[i])
 
    return maximum
arr = [10, 22, 9, 33, 21, 50, 41, 60]
print "Length of lis is", lis(arr)

'''MinMax'''
import time
cnt=0
global a
a = [int(x) for x in input().split()]
def MaxMin(i,j,maxi,mini):
    global cnt
    cnt=cnt+j
    if i==j:
        maxi=mini=a[i]
    elif i<=j-1:
        if a[i]<a[j]:
            maxi=a[j]
            mini=a[i]
        else:
            maxi=a[i]
            mini=a[j]
    else:
        mid=(i+j)//2
        MaxMin(i,mid,maxi,mini)
        MaxMin(mid+1,j,max1,min1)
        if maxi<max1:
            maxi=max1
        if mini>min1:
            mini=min1
    return maxi,mini

start=time.time()
maxi=mini=0
n=len(a)
j=n-1
i=0
c,d=MaxMin(i,j,maxi,mini)
print("Maximum Number is ",c,"Minimum Number is ",d)
print("The Number Of Comparissions is",cnt)
end=time.time()
print("Time Taken To Execute is ",end-start)
Maximum Number is 5 Minimum Number is 1 The Number Of Comparissions is 4 Time Taken To Execute is 0.0007982254028320312
# N Queen Problem
import math
x = {}
n = 8
def place(k, i):
    if (i in x.values()):
        return False
    j = 1
    while(j < k):
        if abs(x[j]-i) == abs(j-k):
            return False
        j+=1
    return True
def clear(k):
    for i in range(k,n+1):
        x[i]=None
a=[]
def NQueens(k=1):
    for i in range(1, n + 1):
        clear(k)
        if place(k, i):
            x[k] = i
            if (k==n):
                b=[]
                for j in x:
                    b.append(x[j]-1)
                a.append(b)
            else:
                NQueens(k+1)
NQueens()

print(a)
[[0, 4, 7, 5, 2, 6, 1, 3], [0, 5, 7, 2, 6, 3, 1, 4], [0, 6, 3, 5, 7, 1, 4, 2], [0, 6, 4, 7, 1, 3, 5, 2], [1, 3, 5, 7, 2, 0, 6, 4], [1, 4, 6, 0, 2, 7, 5, 3], [1, 4, 6, 3, 0, 7, 5, 2], [1, 5, 0, 6, 3, 7, 2, 4], [1, 5, 7, 2, 0, 3, 6, 4], [1, 6, 2, 5, 7, 4, 0, 3], [1, 6, 4, 7, 0, 3, 5, 2], [1, 7, 5, 0, 2, 4, 6, 3], [2, 0, 6, 4, 7, 1, 3, 5], [2, 4, 1, 7, 0, 6, 3, 5], [2, 4, 1, 7, 5, 3, 6, 0], [2, 4, 6, 0, 3, 1, 7, 5], [2, 4, 7, 3, 0, 6, 1, 5], [2, 5, 1, 4, 7, 0, 6, 3], [2, 5, 1, 6, 0, 3, 7, 4], [2, 5, 1, 6, 4, 0, 7, 3], [2, 5, 3, 0, 7, 4, 6, 1], [2, 5, 3, 1, 7, 4, 6, 0], [2, 5, 7, 0, 3, 6, 4, 1], [2, 5, 7, 0, 4, 6, 1, 3], [2, 5, 7, 1, 3, 0, 6, 4], [2, 6, 1, 7, 4, 0, 3, 5], [2, 6, 1, 7, 5, 3, 0, 4], [2, 7, 3, 6, 0, 5, 1, 4], [3, 0, 4, 7, 1, 6, 2, 5], [3, 0, 4, 7, 5, 2, 6, 1], [3, 1, 4, 7, 5, 0, 2, 6], [3, 1, 6, 2, 5, 7, 0, 4], [3, 1, 6, 2, 5, 7, 4, 0], [3, 1, 6, 4, 0, 7, 5, 2], [3, 1, 7, 4, 6, 0, 2, 5], [3, 1, 7, 5, 0, 2, 4, 6], [3, 5, 0, 4, 1, 7, 2, 6], [3, 5, 7, 1, 6, 0, 2, 4], [3, 5, 7, 2, 0, 6, 4, 1], [3, 6, 0, 7, 4, 1, 5, 2], [3, 6, 2, 7, 1, 4, 0, 5], [3, 6, 4, 1, 5, 0, 2, 7], [3, 6, 4, 2, 0, 5, 7, 1], [3, 7, 0, 2, 5, 1, 6, 4], [3, 7, 0, 4, 6, 1, 5, 2], [3, 7, 4, 2, 0, 6, 1, 5], [4, 0, 3, 5, 7, 1, 6, 2], [4, 0, 7, 3, 1, 6, 2, 5], [4, 0, 7, 5, 2, 6, 1, 3], [4, 1, 3, 5, 7, 2, 0, 6], [4, 1, 3, 6, 2, 7, 5, 0], [4, 1, 5, 0, 6, 3, 7, 2], [4, 1, 7, 0, 3, 6, 2, 5], [4, 2, 0, 5, 7, 1, 3, 6], [4, 2, 0, 6, 1, 7, 5, 3], [4, 2, 7, 3, 6, 0, 5, 1], [4, 6, 0, 2, 7, 5, 3, 1], [4, 6, 0, 3, 1, 7, 5, 2], [4, 6, 1, 3, 7, 0, 2, 5], [4, 6, 1, 5, 2, 0, 3, 7], [4, 6, 1, 5, 2, 0, 7, 3], [4, 6, 3, 0, 2, 7, 5, 1], [4, 7, 3, 0, 2, 5, 1, 6], [4, 7, 3, 0, 6, 1, 5, 2], [5, 0, 4, 1, 7, 2, 6, 3], [5, 1, 6, 0, 2, 4, 7, 3], [5, 1, 6, 0, 3, 7, 4, 2], [5, 2, 0, 6, 4, 7, 1, 3], [5, 2, 0, 7, 3, 1, 6, 4], [5, 2, 0, 7, 4, 1, 3, 6], [5, 2, 4, 6, 0, 3, 1, 7], [5, 2, 4, 7, 0, 3, 1, 6], [5, 2, 6, 1, 3, 7, 0, 4], [5, 2, 6, 1, 7, 4, 0, 3], [5, 2, 6, 3, 0, 7, 1, 4], [5, 3, 0, 4, 7, 1, 6, 2], [5, 3, 1, 7, 4, 6, 0, 2], [5, 3, 6, 0, 2, 4, 1, 7], [5, 3, 6, 0, 7, 1, 4, 2], [5, 7, 1, 3, 0, 6, 4, 2], [6, 0, 2, 7, 5, 3, 1, 4], [6, 1, 3, 0, 7, 4, 2, 5], [6, 1, 5, 2, 0, 3, 7, 4], [6, 2, 0, 5, 7, 4, 1, 3], [6, 2, 7, 1, 4, 0, 5, 3], [6, 3, 1, 4, 7, 0, 2, 5], [6, 3, 1, 7, 5, 0, 2, 4], [6, 4, 2, 0, 5, 7, 1, 3], [7, 1, 3, 0, 6, 4, 2, 5], [7, 1, 4, 2, 0, 6, 3, 5], [7, 2, 0, 5, 1, 4, 6, 3], [7, 3, 0, 2, 5, 1, 6, 4]]
class stack:
    def __init__(self):
        self.top=-1
        self.items=[]
    def push(self,i):
        self.items.append(i)
        self.top+=1
    def pop(self):
        if self.top==-1:
            print("UnderFlow")
        else :
            self.top-=1
    def show(self):
        print(self.items)
s1=stack()
s1.push(1)
s1.push(6)
s1.push(5)
s1.push(4)
s1.show()
[1, 6, 5, 4]
class Queue:
    def __init__(self):
        self.rear=0
        self.items=[]
    def push(self,i):
        self.items.append(i)
        self.rear+=1
    def pop(self):
        if self.rear==0:
            print("UnderFlow")
        else :
            self.items= self.items[1:]
            self.rear-=1
    def show(self):
        print(self.items)
s1=Queue()
s1.push(1)
s1.push(6)
s1.push(25)
s1.push(46)
s1.pop()
s1.show()
[6, 25, 46]
def initialize(n):
    for key in ['queen','row','col','nwtose','swtone']:
    board[key] = {}
  for i in range(n):
    board['queen'][i] = -1
    board['row'][i] = 0
    board['col'][i] = 0
  for i in range(-(n-1),n):
    board['nwtose'][i] = 0
  for i in range(2*n-1):
    board['swtone'][i] = 0

def printboard():
  for row in sorted(board['queen'].keys()):
    print((row,board['queen'][row]))

def free(i,j):
  return(board['row'][i] == 0 and board['col'][j] == 0 and
          board['nwtose'][j-i] == 0 and board['swtone'][j+i] == 0)

def addqueen(i,j):
  board['queen'][i] = j
  board['row'][i] = 1
  board['col'][j] = 1
  board['nwtose'][j-i] = 1
  board['swtone'][j+i] = 1

def undoqueen(i,j):
  board['queen'][i] = -1
  board['row'][i] = 0
  board['col'][j] = 0
  board['nwtose'][j-i] = 0
  board['swtone'][j+i] = 0

def placequeen(i):
  n = len(board['queen'].keys())
  for j in range(n):
    if free(i,j):
      addqueen(i,j)
      if i == n-1:
        return(True)
      else:
        extendsoln = placequeen(i+1)
      if extendsoln:
        return(True)
      else:
        undoqueen(i,j)
  else:
    return(False)

board = {}
n = int(input("How many queens? "))
initialize(n)
if placequeen(0):
    printboard()

File "<tokenize>", line 4 for i in range(n): ^ IndentationError: unindent does not match any outer indentation level
def ssum(list,sum):
    current = "";
    ssum_h(list,len(list),current,sum)

def ssum_h(list,n,subset,sum):
    if sum==0:
        print(subset)
        return 
    if n==0:
        return 
    if list[n-1]<=sum:
        ssum_h(list,n-1,subset,sum)
        ssum_h(list,n-1,subset+str(list[n-1])+" ",sum-list[n-1])
    else:
        ssum_h(list,n-1,subset,sum)

if __name__ == "__main__":
    list = [int(x) for x in input().split()]
    sum = int(input())
    ssum(list,sum)
mat=[[" "," "," "," "," "," "," "," "] for i in range(8)]
def initialize(n):
  for key in ['queen','row','col','nwtose','swtone']:
    board[key] = {}
  for i in range(n):
    board['queen'][i] = -1
    board['row'][i] = 0
    board['col'][i] = 0
  for i in range(-(n-1),n):
    board['nwtose'][i] = 0
  for i in range(2*n-1):
    board['swtone'][i] = 0

def printboard():
  for row in sorted(board['queen'].keys()):
    #print((row,board['queen'][row]))
    mat[row][board['queen'][row]]="O"

def free(i,j):
  return(board['row'][i] == 0 and board['col'][j] == 0 and
          board['nwtose'][j-i] == 0 and board['swtone'][j+i] == 0)

def addqueen(i,j):
  board['queen'][i] = j
  board['row'][i] = 1
  board['col'][j] = 1
  board['nwtose'][j-i] = 1
  board['swtone'][j+i] = 1

def undoqueen(i,j):
  board['queen'][i] = -1
  board['row'][i] = 0
  board['col'][j] = 0
  board['nwtose'][j-i] = 0
  board['swtone'][j+i] = 0

def placequeen(i):
  n = len(board['queen'].keys())
  for j in range(n):
    if free(i,j):
      addqueen(i,j)
      if i == n-1:
        return(True)
      else:
        extendsoln = placequeen(i+1)
      if extendsoln:
        return(True)
      else:
        undoqueen(i,j)
  else:
    return(False)

board = {}
n = int(input("How many queens? "))
initialize(n)
if placequeen(0):
  printboard()
print()
print()
print()
for k in range(8) : print ("----",end='')
print()
for i in range (8):
	for j in range(8):
		print(mat[i][j],end=' | ')
	print()
	for k in range(8) : print ("----",end='')
	print()
print()
print()
print()

How many queens?
from tkinter import *
import time
import random
root=Tk()
root.title("N QUEENS")
root.iconbitmap('GBP.ico') 
btn,board1,board,cc,ans,count=[],[],{},0,[],0

photo    = PhotoImage(file='''tata.png''')
filename = PhotoImage(file = "win.png")
fn       = PhotoImage(file = "Queen.png")
sol      = PhotoImage(file = "sol.png")
res      = PhotoImage(file = "res.png")

def init():
    for key in ['queen','row','col','nwtose','swtone']:
        board[key] = {}
    for i in range(8):
        board['queen'][i] = -1
        board['row'][i] = 0
        board['col'][i] = 0
    for i in range(-7,8):
        board['nwtose'][i] = 0
    for i in range(17):
        board['swtone'][i] = 0
        
def addqueen(i,j):
     board['queen'][i] = j
     board['row'][i] = 1
     board['col'][j] = 1
     board['nwtose'][j-i] = 1
     board['swtone'][j+i] = 1
     
def undoqueen(i,j):
     board['queen'][i] = -1
     board['row'][i] = 0
     board['col'][j] = 0
     board['nwtose'][j-i] = 0
     board['swtone'][j+i] = 0
     
def placequeen(i):
    for j in range(8):
        if free(i,j):
            addqueen(i,j)
            if i == 7: printboard()
            else: placequeen(i+1)
            undoqueen(i,j)
          
def printboard():
     asa=[]
     for row in sorted(board['queen'].keys()):
         asa.append(board['queen'][row])
     ans.append(asa)
 

def free(i,j):
     return(board['row'][i] == 0 and board['col'][j] == 0 and board['nwtose'][j-i] == 0 and board['swtone'][j+i] == 0)
    
def reset():
    global cc,count,start
    cc,count,start=0,0,time.time()
    init()    
    for i in range(8):
        for j in range(8):
            board1[i][j]=0
            if(i+j)%2==0: col="white"
            else: col='black'
            btn[i][j].configure(image='',height=5,width=10,bg=col)
    canvas.create_rectangle(550,700,100,400,fill='black') 
    
def showall():
    global count
    reset()
    ran=random.randint(0,len(ans)-1)
    ase=ans[ran]
    for i in range(8):
        b=btn[i][ase[i]]
        b.configure(image=photo,height=75,width=72)
    count=8
    
def gui(event):
    global count,cc
    b=event.widget
    x=str(b.cget('textvariable'))
    x,y=int(x[0]),int(x[2])
    if(x+y)%2==0: col="white"
    else: col='black'

    if count >= 8 and board1[x][y]==0 :return
    if board1[x][y]==0:    
        b.configure(image=photo,height=75,width=72)
        if free(x,y)== False: b.configure(bg='red')
        else :
            cc+=1
            addqueen(x,y)
        count+=1
        board1[x][y]=1
    else :
        if b.cget('bg')== 'black' or b.cget('bg')== 'white': 
            undoqueen(x,y)
            if free(x,y)==True : cc-=1
        b.configure(image='',height=5,width=10,bg=col)
        count-=1
        board1[x][y]=0

    if cc == 8 :
        canvas.create_image(500, 550, anchor=E, image=filename)
        st=(time.time()-start)
        st="Time required is : "+str(round(st,1))+' seconds'
        canvas.create_text(350, 640, font=("Times new Roman", 20), text= st,fill='#fffc9c')
        for i in range(8):
            for j in range(8) : board1[i][j]=0
            
'''--------------------Main------------------------'''

for i in range(8):
    board1.append([0,0,0,0,0,0,0,0])
    b=[]
    for j in range(8):
        if(i+j)%2==0: col="white"
        else: col='black'
        b.append(Button(bg=col,height=5,width=10,textvariable=[i,j]))
        b[j].grid(row=i,column=j)
        b[j].bind("<ButtonRelease-1>",gui)
    btn.append(b)
 
init()
placequeen(0)
printboard()
ans=ans[:-1]
init()

canvas = Canvas(root, width = 710, height = 674, bg ="black")
canvas.grid(row=0,column=8,rowspan=8)
imag = canvas.create_image(550, 170, anchor=E, image=fn)
st="Place 8 Queens on the Chess Board"
canvas.create_text(345, 300, font=("Old English Text MT", 20), text= st,anchor=N,fill='#fffc9c')
st='''Condition : None of the Queen's path should overlap '''
canvas.create_text(345, 340, font=("Times New Roman", 10), text= st,anchor=N,fill='white')

button1 = Button( command=showall,  anchor = W)
button1.configure(image=sol,width = 150,height=50,bg='black', relief = FLAT,activebackground='black')
canvas.create_window(180, 370, anchor=NW, window=button1)

button2 = Button( command=reset,  anchor = W)
button2.configure(image=res,width = 150,height=50,bg='black', relief = FLAT,activebackground='black')
canvas.create_window(360, 370, anchor=NW, window=button2)

start=time.time()
root.mainloop()

--------------------------------------------------------------------------- TclError Traceback (most recent call last) <ipython-input-2-96b8c19652f4> in <module>() 2 import time 3 board1=[] ----> 4 root=Tk() 5 root.title("N QUEENS") 6 count=0 /ext/anaconda3/lib/python3.5/tkinter/__init__.py in __init__(self, screenName, baseName, className, useTk, sync, use) 1874 baseName = baseName + ext 1875 interactive = 0 -> 1876 self.tk = _tkinter.create(screenName, baseName, className, interactive, wantobjects, useTk, sync, use) 1877 if useTk: 1878 self._loadtk() TclError: no display name and no $DISPLAY environment variable
#Dynamic Fac 
has=[0 for x in range(1000)]
tc=int(input())
def fac(x):
    if x ==1 or x==0 : return 1
    elif has[x]==0:
        has[x]=x*fac(x-1)
        return has[x]
    else: return has[x]
for tt in range(tc):
    f=int(input())
    print (fac(f))

120
'''Sum of subsets'''
import random 

def sub(lst,n,subset,sums):
    if sum==0:
        print(subset)
        return
    if n==0:
        return
    if lst[n-1]<=sums :
        sub(lst,n-1,subset,sums)
        sub(lst,n-1,subset+str(lst[n-1])+" ",sums-lst[n-1])
    else:
        sub(lst,n-1,subset,sums)
subset=''
l=random.sample(range(10),10)
sums=5
sub(l,10,subset,sums)