#Given a positive integer n between 1 and 9, generate the #permuations of the se

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()', determine how many seconds
#passes when running this code for n=3, 4, 5, and 6.

#Hints: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.

def permute(n):
startTime=time.clock()
# BODY OF python FUNCTION i need GOES HERE using
# desriptive variable names and comments so i can follow
endTime= time.clock()
print endTime-startTime
    
# HELPER FUNCTIONS MAY GO HERE if needed

Explanation / Answer

# Use Python v 2.7, read the comments to understand...copy it and try on some online python compiler

import time
from operator import itemgetter

DEBUG = False # like the built-in __debug__

def permute(n):
startTime = time.clock();
"""permutations by swapping. Yields: perm, sign"""
sign = 1
p = [[i, 0 if i == 0 else -1] # [num, direction]
for i in range(n)]

if DEBUG: print ' #', p
yield tuple(pp[0] for pp in p), sign

while any(pp[1] for pp in p): # moving
i1, (n1, d1) = max(((i, pp) for i, pp in enumerate(p) if pp[1]),
key=itemgetter(1))
sign *= -1
if d1 == -1:
# Swap down
i2 = i1 - 1
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the First or last
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
if i2 == 0 or p[i2 - 1][0] > n1:
# The direction of the chosen element is set to zero
p[i2][1] = 0
elif d1 == 1:
# Swap up
i2 = i1 + 1
p[i1], p[i2] = p[i2], p[i1]
# If this causes the chosen element to reach the first or Last
# position within the permutation, or if the next element in the
# same direction is larger than the chosen element:
if i2 == n - 1 or p[i2 + 1][0] > n1:
# The direction of the chosen element is set to zero
p[i2][1] = 0
if DEBUG: print ' #', p
yield tuple(pp[0] for pp in p), sign

for i3, pp in enumerate(p):
n3, d3 = pp
if n3 > n1:
pp[1] = 1 if i3 < i2 else -1
if DEBUG: print ' # Set Moving'
endTime = time.clock();
print endTime - startTime


if __name__ == '__main__':
from itertools import permutations
#Here you can change the value from 1 to 9 to see the list of all permutation for n.
# e.g --> for n in (1,): OR for n in (2,): and so on...
# e.g ---> for n in (1,2,3,4) ...etc. you get the idea.
for n in (1,):
print ' Permutations and sign of %i items' % n
sp = set()
for i in permute(n):
sp.add(i[0])
print('Perm: %r Sign: %2i' % i)
#if DEBUG: raw_input('?')
# Test
p = set(permutations(range(n)))
assert sp == p, 'Two methods of generating permutations do not agree'

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.