Practice Problem 6-Isomorphic Numbers
ISOMORPHIC NUMBERS
Given ‘n’ integers, write an algorithm and the subsequent Python code to print all numbers that are isomorphic to the first number. Two numbers with non-distinct (numbers in which digits get repeated) are said to be isomorphic if they have the same number of digits in it and the sets of positions having the same digits are equal.. For example:
• 12321 is isomorphic to 83538 .
Both the numbers are of length five. In 12321, positions 2 and 4 have the same digit 2, Positions 1 and 5 have same digit 1. Hence the set of positions having the same digit are {{1,5},{2,4}. Similarly , for the number 83538, the set of positions having the same digit is {{1,5}, {2,4}}.
• 1232 is not isomorphic to 2342 because set of places having same digits for 1232 is {{2, 4}} and for 2342 is {{1, 4}} (digits are numbered from left to right starting from 1).
• 12 is not isomorphic to 10.
Write a function to check whether two numbers are isomorphic. If none of the numbers are isomorphic then print ‘No isomorphic’.
Input Format
First line contains the number of elements, n
Next ‘n’ line contains the numbers
Output Format
Print first number in the first line
Next few lines contain the numbers that are isomorphic to first number.
If the none of the numbers are not isomorphic, then Print “No isomorphic”
PROGRAM
n = int(input())
def isoset(x):
l= set()
for a in x:
if x.count(a)>1:
p= list()
for b in range(len(x)):
if a==x[b]:
p.append(b+1)
if len(p)>0:
l.add(tuple(p))
if len(l)>1:
return(l)
else:
return('n')
fno = input().rstrip()
f = 0
l=[]
for a in range(1,n):
x = input().rstrip()
if len(fno)==len(x) and isoset(fno)!='n' and isoset(x)!='n' and isoset(fno)==isoset(x):
l.append(x)
f=1
if f == 0:
print('No isomorphic')
exit()
else:
print(fno)
for a in l:
print(a)
INPUT
- Number of elements, n
- ‘n’ numbers
OUTPUT
- Print first number in the first line
- Next few lines contain the numbers that are isomorphic to first number.
- If none of the numbers are isomorphic, then Print “No isomorphic”
PROCESSING
for a in range(1,n):
x = input().rstrip()
if len(fno)==len(x) and isoset(fno)!=’n’ and isoset(x)!=’n’ and isoset(fno)==isoset(x):
l.append(x)
f=1
if f == 0:
print(‘No isomorphic’)
exit()
else:
print(fno)
for a in l:
print(a)
x = input().rstrip()
if len(fno)==len(x) and isoset(fno)!=’n’ and isoset(x)!=’n’ and isoset(fno)==isoset(x):
l.append(x)
f=1
if f == 0:
print(‘No isomorphic’)
exit()
else:
print(fno)
for a in l:
print(a)
PSEUDOCODE
1.START
2.INPUT n
3.DEFINE FUNCTION isoset(x):
3.1 DEFINE l as an empty set
3.2 FOR a in x:
3.2.1 CHECK IF COUNT OF a in x>1:
3.2.1.1 DEFINE p as an empty set
3.2.1.2 FOR b in range(len(x)):
CHECK IF a==x[b]:
APPEND (b+1) to p
3.2.1.3 CHECK IF len(p)>0:
ADD tuple(p) to l
3.3 CHECK IF len(l)>1:
3.3.1 RETURN (l)
3.4 ELSE:
3.4.1 RETURN (‘n’)
4.INPUT fno (string)
5. DEFINE f = 0
6. DEFINE l as an empty set
7.FOR a in range(1,n):
7.1 INPUT x (string)
7.2 CHECK IF len(fno)==len(x) and isoset(fno)!=’n’ and isoset(x)!=’n’ and isoset(fno)==isoset(x):
7.2.1 APPEND x to l
7.2.2 SET f=1
8. CHECK IF f == 0:
8.1 DISPLAY ‘No isomorphic’
8.2 EXIT
9. ELSE:
9.1 DISPLAY fno
9.2 FOR a in l:
9.2.1 DISPLAY a
2.INPUT n
3.DEFINE FUNCTION isoset(x):
3.1 DEFINE l as an empty set
3.2 FOR a in x:
3.2.1 CHECK IF COUNT OF a in x>1:
3.2.1.1 DEFINE p as an empty set
3.2.1.2 FOR b in range(len(x)):
CHECK IF a==x[b]:
APPEND (b+1) to p
3.2.1.3 CHECK IF len(p)>0:
ADD tuple(p) to l
3.3 CHECK IF len(l)>1:
3.3.1 RETURN (l)
3.4 ELSE:
3.4.1 RETURN (‘n’)
4.INPUT fno (string)
5. DEFINE f = 0
6. DEFINE l as an empty set
7.FOR a in range(1,n):
7.1 INPUT x (string)
7.2 CHECK IF len(fno)==len(x) and isoset(fno)!=’n’ and isoset(x)!=’n’ and isoset(fno)==isoset(x):
7.2.1 APPEND x to l
7.2.2 SET f=1
8. CHECK IF f == 0:
8.1 DISPLAY ‘No isomorphic’
8.2 EXIT
9. ELSE:
9.1 DISPLAY fno
9.2 FOR a in l:
9.2.1 DISPLAY a
Comments
Post a Comment