#! /usr/bin/env python # def i4vec_permute ( n, p, a ): #*****************************************************************************80 # ## I4VEC_PERMUTE permutes an I4VEC in place. # # Discussion: # # An I4VEC is a vector of I4's. # # This routine permutes an array of integer "objects", but the same # logic can be used to permute an array of objects of any arithmetic # type, or an array of objects of any complexity. The only temporary # storage required is enough to store a single object. The number # of data movements made is N + the number of cycles of order 2 or more, # which is never more than N + N/2. # # Example: # # Input: # # N = 5 # P = ( 1, 3, 4, 0, 2 ) # A = ( 1, 2, 3, 4, 5 ) # # Output: # # A = ( 2, 4, 5, 1, 3 ). # # Licensing: # # This code is distributed under the GNU LGPL license. # # Modified: # # 24 May 2015 # # Author: # # John Burkardt # # Parameters: # # Input, integer N, the number of objects. # # Input, integer P[N], the permutation. P(I) = J means # that the I-th element of the output array should be the J-th # element of the input array. # # Input, integer A[N], the array to be permuted. # # Output, integer A[N], the permuted array. # from perm0_check import perm0_check from sys import exit check = perm0_check ( n, p ); if ( not check ): print ( '' ) print ( 'I4VEC_PERMUTE - Fatal error!' ) print ( ' PERM0_CHECK rejects the permutation.' ) exit ( 'I4VEC_PERMUTE - Fatal error!' ) # # In order for the sign negation trick to work, we need to assume that the # entries of P are strictly positive. Presumably, the lowest number is 0. # So temporarily add 1 to each entry to force positivity. # for i in range ( 0, n ): p[i] = p[i] + 1 # # Search for the next element of the permutation that has not been used. # for istart in range ( 1, n + 1 ): if ( p[istart-1] < 0 ): continue elif ( p[istart-1] == istart ): p[istart-1] = - p[istart-1] else: a_temp = a[istart-1]; iget = istart; # # Copy the new value into the vacated entry. # while ( True ): iput = iget iget = p[iget-1] p[iput-1] = - p[iput-1] if ( iget < 1 or n < iget ): print ( '' ) print ( 'I4VEC_PERMUTE - Fatal error!' ) print ( ' Entry IPUT = %d has' % ( iput ) ) print ( ' an illegal value IGET = %d.' % (iget ) ) exit ( 'I4VEC_PERMUTE - Fatal error!' ) if ( iget == istart ): a[iput-1] = a_temp break a[iput-1] = a[iget-1] # # Restore the signs of the entries. # for i in range ( 0, n ): p[i] = - p[i] # # Restore the entries. # for i in range ( 0, n ): p[i] = p[i] - 1 return a def i4vec_permute_test ( ): #*****************************************************************************80 # ## I4VEC_PERMUTE_TEST tests I4VEC_PERMUTE. # # Licensing: # # This code is distributed under the GNU LGPL license. # # Modified: # # 25 October 2014 # # Author: # # John Burkardt # import platform from i4vec_print import i4vec_print from i4vec_uniform_ab import i4vec_uniform_ab from perm0_uniform import perm0_uniform n = 12 print ( '' ) print ( 'I4VEC_PERMUTE_TEST' ) print ( ' Python version: %s' % ( platform.python_version ( ) ) ) print ( ' I4VEC_PERMUTE reorders an I4VEC' ) print ( ' according to a given permutation.' ) b = 0 c = n seed = 123456789 a, seed = i4vec_uniform_ab ( n, b, c, seed ) i4vec_print ( n, a, ' A[*], before rearrangement:' ) p, seed = perm0_uniform ( n, seed ) i4vec_print ( n, p, ' Permutation vector P[*]:' ) a = i4vec_permute ( n, p, a ) i4vec_print ( n, a, ' A[P[*]]:' ) # # Terminate. # print ( '' ) print ( 'I4VEC_PERMUTE_TEST:' ) print ( ' Normal end of execution.' ) return if ( __name__ == '__main__' ): from timestamp import timestamp timestamp ( ) i4vec_permute_test ( ) timestamp ( )