#!/usr/bin/python 
# 
#    This program will generate a random permutation of the integers
#  { 1, ..., n } for a user specified integer n.  We assume that
#  user inputs a positive integer (if it's negative then we'll get
#  an error as the program executes).  
#
#    We use the Markov chain Monte Carlo method for generating the
#  random permuation by performing random swaps of adjacent elements.  
#

#  import the math library for the logartihm function
import math

#  import the pseudorandom number generator
import random

#  get input from the user   
n = int(input ("\nEnter the length of the permutation: "))

#  initialize with the identity permutation,  recall that 
#    range(1,n+1)  
#  will generate the range of numbers 1, 2, 3, ..., n 
nums = list(range(1,n+1))

#  create the permutation 
iters = int(12 * n**3 * math.log(n) + 1)

for i in range(iters): 
    if random.uniform(0,1) <= .5:    #  Flip a coin, and if heads swap
                                     # a random adjacent pair of elements.  
        k = random.randint(0,n-2)
        #  swap the two adjacent positions 
        nums [k], nums [k + 1]  =  nums [k + 1], nums [k] 
    
print "\n",str(nums).strip('[]'),"\n\n"