Question
#Given a positive integer n between 1 and 9, generate the #permuations of the set {1,2,3,4,...,n} using the Johnson-Trotter #algorithm. #Using 'import time' and 'time.clock()',
#Given a positive integer n between 1 and 9, generate the #permuations of the set {1,2,3,4,...,n} using the Johnson-Trotter #algorithm.
#Using 'import time' and 'time.clock()', determine how many seconds #passes when running this code for n=3, 4, 5, and 6.
#Hints: USING INFO BASED ON THE JOHNSON-TROTTER ALGORITHM. I wrote the #following helper functions. You may find this approach useful. #1. Is a given element mobile? Given a permutation with arrows #and a position, return true if the element in that position is #mobile and false if it is not mobile. #2. Is any element mobile? Given a permutation with arrows, #return true if any element is mobile and false if no element is #mobile. #3. What is the position of the largest mobile element? Given a #permutation with arrows, return the position of the largest mobile #element. #4. What is the next permutation? Given a permutation with arrows, #return the next permutation with arrows.
import time
#Given a number n from 1 to 9, print each of the permuations of #1, 2, ... n to the screen. Calculate the time required to do so, #and print that time to the screen as well.
*SO THE FOLLOWING CODE SEEMS TO WORK FOR WHAT I NEED BUT
MY QUESTION IS DOES THIS ACTUALLY USE THE JOHNSON-TROTTER
ALGORITHM AND IF SO CAN YOU PLEASE COMMENT THIS OUT IN A
DETAILED MANNER SO I CAN UNDERSTAND WHAT IS GOING ON? FOR EXAMPLE,
I HAVE NO IDEA WHAT THE ARGUEMENT (RECL) DOES OR STANDS FOR. WHAT DO THE
M AND P VARIABLES REPRESENT AND HOW DOES NUM DIFFER FROM N AND IS IT POSSIBLE TO USE (n) INSTEAD OF (num) AS THE ARGUEMENT FOR THE FUNCTION PERMUTE? THANK YOU FOR ANY HELP!!*
def permute(num): # startTime=time.clock() if (len(num) == 0): return [] if (len(num) == 1): return [num] l = [] # empty list that will store current permute for i in range(len(num)): m = num[i] reml = num[:i] + num[i+1:]
for p in permute(reml): l.append([m] + p) return l # endTime= time.clock() # print endTime-startTime
programStart = time.clock() n=int(input("Enter an integer from 1 to 9: ")) l = [] for i in range(1,n+1,1): l.append(i) permutationStart = time.clock() for p in permute(l): print p permutationEnd = time.clock() programEnd = time.clock() #endTime= time.clock() #print endTime-startTime print("Total time taken for computing permutations: %f seconds."%(permutationEnd-permutationStart)) print("Total time taken for program: %f seconds."%(programEnd-programStart))
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started