Posts: 94
Threads: 8
Joined: Jan 2020
Hi,
How can we write program for below probelm to accept input and output accordingly:-
We have a list of pair{i,j} of teams where i and j are the
teams who will play their first match together in the tournament.There are 2*N teams numbered 0 to 2*N-1.management wants to make this list
good looking before world cup starts .A good looking list has team pairs like {0,1},{2,3},{4,5},{6,7}...{2*N-2,2*N-1) only.
Note that order doesn't matter ,{0,1} nd {1,0} are both valid good looking pair.
Given a list of team pairs,what is the minimum number of team swaps needed to make it a good looking list.
Input:-
First line contains one integer 1<=N<=1000,number of pairs.
Next N line contains 2 space separated integers representing a pair {i,j} in current list.
Output Format:-
Print one integer,that is minimum number of swaps needed to make the list good looking
Sample Input 1:
3
1 3
0 2
4 5
Sample Output 1:
1
Explanation:
If we swap 0 and 3 list becomes (1,0),(3,2) and (4,5),which is a good looking list.
Sample Input 2:
2
3 2
0 1
Sample Output 2:
0
Explanation:
List is already good looking.
Posts: 1,822
Threads: 2
Joined: Apr 2017
What have you tried or at least thought about?
Posts: 94
Threads: 8
Joined: Jan 2020
I tried below but it is not satisfying given scenarios:-
[code]
# This function updates
# indexes of elements 'a' and 'b'
def updateindex(index,a,ai,b,bi):
index[a] = ai
index[b] = bi
# This function returns minimum
# number of swaps required to arrange
# all elements of arr[i..n]
# become aranged
def minSwapsUtil(arr,pairs,index,i,n):
# If all pairs procesed so
# no swapping needed return 0
if (i > n):
return 0
# If current pair is valid so
# DO NOT DISTURB this pair
# and move ahead.
if (pairs[arr[i]] == arr[i+1]):
return minSwapsUtil(arr, pairs, index, i+2, n)
# If we reach here, then arr[i]
# and arr[i+1] don't form a pair
# Swap pair of arr[i] with
# arr[i+1] and recursively compute
# minimum swap required
# if this move is made.
one = arr[i+1]
indextwo = i+1
indexone = index[pairs[arr[i]]]
two = arr[index[pairs[arr[i]]]]
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indexone, two, indextwo)
a = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous configuration.
# Also restore the
# previous indices,
# of one and two
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indextwo, two, indexone)
one = arr[i]
indexone = index[pairs[arr[i+1]]]
# Now swap arr[i] with pair
# of arr[i+1] and recursively
# compute minimum swaps
# required for the subproblem
# after this move
two = arr[index[pairs[arr[i+1]]]]
indextwo = i
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indexone, two, indextwo)
b = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous
# configuration. Also restore
# 3 the previous indices,
# of one and two
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indextwo, two, indexone)
# Return minimum of two cases
return 1 + min(a, b)
# Returns minimum swaps required
def minSwaps(n,pairs,arr):
index=[] # To store indices of array elements
for i in range(2*n+1+1):
index.append(0)
# Store index of each
# element in array index
for i in range(1,2*n+1):
index[arr[i]] = i
# Call the recursive function
return minSwapsUtil(arr, pairs, index, 1, 2*n)
# Driver code
# For simplicity, it is
# assumed that arr[0] is
# not used. The elements
# from index 1 to n are
# only valid elements
arr = [0, 3, 5, 6, 4, 1, 2]
# if (a, b) is pair than
# we have assigned elements
# in array such that
# pairs[a] = b and pairs[b] = a
pairs= [0, 3, 6, 1, 5, 4, 2]
m = len(pairs)
n = m//2 # Number of pairs n
# is half of total elements
# If there are n
# elements in array, then
# there are n pairs
print("Min swaps required is ",minSwaps(n, pairs, arr))
[code\]
Posts: 1,344
Threads: 2
Joined: May 2019
Come on. You have 37 posts. You know you need to post using the Python tags as otherwise you lose all indentation
Posts: 94
Threads: 8
Joined: Jan 2020
# This function updates
# indexes of elements 'a' and 'b'
def updateindex(index,a,ai,b,bi):
index[a] = ai
index[b] = bi
# This function returns minimum
# number of swaps required to arrange
# all elements of arr[i..n]
# become aranged
def minSwapsUtil(arr,pairs,index,i,n):
# If all pairs procesed so
# no swapping needed return 0
if (i > n):
return 0
# If current pair is valid so
# DO NOT DISTURB this pair
# and move ahead.
if (pairs[arr[i]] == arr[i+1]):
return minSwapsUtil(arr, pairs, index, i+2, n)
# If we reach here, then arr[i]
# and arr[i+1] don't form a pair
# Swap pair of arr[i] with
# arr[i+1] and recursively compute
# minimum swap required
# if this move is made.
one = arr[i+1]
indextwo = i+1
indexone = index[pairs[arr[i]]]
two = arr[index[pairs[arr[i]]]]
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indexone, two, indextwo)
a = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous configuration.
# Also restore the
# previous indices,
# of one and two
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indextwo, two, indexone)
one = arr[i]
indexone = index[pairs[arr[i+1]]]
# Now swap arr[i] with pair
# of arr[i+1] and recursively
# compute minimum swaps
# required for the subproblem
# after this move
two = arr[index[pairs[arr[i+1]]]]
indextwo = i
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indexone, two, indextwo)
b = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous
# configuration. Also restore
# 3 the previous indices,
# of one and two
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indextwo, two, indexone)
# Return minimum of two cases
return 1 + min(a, b)
# Returns minimum swaps required
def minSwaps(n,pairs,arr):
index=[] # To store indices of array elements
for i in range(2*n+1+1):
index.append(0)
# Store index of each
# element in array index
for i in range(1,2*n+1):
index[arr[i]] = i
# Call the recursive function
return minSwapsUtil(arr, pairs, index, 1, 2*n)
# Driver code
# For simplicity, it is
# assumed that arr[0] is
# not used. The elements
# from index 1 to n are
# only valid elements
arr = [0, 3, 5, 6, 4, 1, 2]
# if (a, b) is pair than
# we have assigned elements
# in array such that
# pairs[a] = b and pairs[b] = a
pairs= [0, 3, 6, 1, 5, 4, 2]
m = len(pairs)
n = m//2 # Number of pairs n
# is half of total elements
# If there are n
# elements in array, then
# there are n pairs
print("Min swaps required is ",minSwaps(n, pairs, arr))
Posts: 1,344
Threads: 2
Joined: May 2019
Your code will fail - lines 5 and 6 need to be indented, or else function in line 3 has no body. Function starting line 13 likewise has no body, follwed by an invalid if statement, basically you have posted code that again has no indentations.
Here, fixed your indentation
# This function updates
# indexes of elements 'a' and 'b'
def updateindex(index,a,ai,b,bi):
index[a] = ai
index[b] = bi
# This function returns minimum
# number of swaps required to arrange
# all elements of arr[i..n]
# become aranged
def minSwapsUtil(arr,pairs,index,i,n):
# If all pairs procesed so
# no swapping needed return 0
if (i > n):
return 0
# If current pair is valid so
# DO NOT DISTURB this pair
# and move ahead.
if (pairs[arr[i]] == arr[i+1]):
return minSwapsUtil(arr, pairs, index, i+2, n)
# If we reach here, then arr[i]
# and arr[i+1] don't form a pair
# Swap pair of arr[i] with
# arr[i+1] and recursively compute
# minimum swap required
# if this move is made.
one = arr[i+1]
indextwo = i+1
indexone = index[pairs[arr[i]]]
two = arr[index[pairs[arr[i]]]]
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indexone, two, indextwo)
a = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous configuration.
# Also restore the
# previous indices,
# of one and two
arr[i+1],arr[indexone]=arr[indexone],arr[i+1]
updateindex(index, one, indextwo, two, indexone)
one = arr[i]
indexone = index[pairs[arr[i+1]]]
# Now swap arr[i] with pair
# of arr[i+1] and recursively
# compute minimum swaps
# required for the subproblem
# after this move
two = arr[index[pairs[arr[i+1]]]]
indextwo = i
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indexone, two, indextwo)
b = minSwapsUtil(arr, pairs, index, i+2, n)
# Backtrack to previous
# configuration. Also restore
# 3 the previous indices,
# of one and two
arr[i],arr[indexone]=arr[indexone],arr[i]
updateindex(index, one, indextwo, two, indexone)
# Return minimum of two cases
return 1 + min(a, b)
# Returns minimum swaps required
def minSwaps(n,pairs,arr):
index=[] # To store indices of array elements
for i in range(2*n+1+1):
index.append(0)
# Store index of each
# element in array index
for i in range(1,2*n+1):
index[arr[i]] = i
# Call the recursive function
return minSwapsUtil(arr, pairs, index, 1, 2*n)
# Driver code
# For simplicity, it is
# assumed that arr[0] is
# not used. The elements
# from index 1 to n are
# only valid elements
arr = [0, 3, 5, 6, 4, 1, 2]
# if (a, b) is pair than
# we have assigned elements
# in array such that
# pairs[a] = b and pairs[b] = a
pairs= [0, 3, 6, 1, 5, 4, 2]
m = len(pairs)
n = m//2 # Number of pairs n
# is half of total elements
# If there are n
# elements in array, then
# there are n pairs
print("Min swaps required is ",minSwaps(n, pairs, arr))Output: Min swaps required is 2
Posts: 94
Threads: 8
Joined: Jan 2020
ok,but this program is not giving desired results considering the problem stated here or input/output and to cover sample input1,2 and desired output1,2.
Thanks
Posts: 1,822
Threads: 2
Joined: Apr 2017
What have you done to debug the problem then?
Posts: 94
Threads: 8
Joined: Jan 2020
no sorry i am not sure how can e get those sample input/output 1,2 scenarios here any idea how can we modify this program to make it work as per desired sample input/output cases here?
Posts: 1,822
Threads: 2
Joined: Apr 2017
You need to spend some time trying to work out why the program isn't working as you want - we aren't here to do the work for you. Start by adding some extra print statements, to check that your variables have the values you expect and that the right branches are being entered. That will help narrow down where the problem is.
|
