Array cyclic shift problem

About array cyclic shift , stay Draw lessons from articles I learned three solutions in .
First, the first circular transposition algorithm , Not much .
Let's start with the second algorithm

Triple inversion algorithm :

The triple inversion algorithm completes the cyclic shift through triple inversion , For example, array [1,2,3,4,5], Then move three steps to the left , This can be done through the following functions :
reverse(0,2) ->[3,2,1,4,5]
reverse(2,4) ->[3,2,1,5,4]
reverse(0,4) ->[4,5,1,2,3]
If the number of steps is recorded as p, Array has n Number , Then there are :
reverse(0,p-1)
reverse(p,n-1)
reverse(0,n-1)
Indeed, before we look at the shift , The result after shift , You will find that the number of steps divides the array into two parts , Then the position of the two parts changed , The principle of position exchange achieved after three reversals can be understood in conjunction with the palm turning Algorithm :
Three reverses –> Palm turning algorithm :
At first, the palm was on our face , The left hand is on the right , First turn your left hand upside down ( Palm outward , Palm back to our face ), Turn your right hand over ( Same as left hand ), Finally, turn both hands at the same time , At this time, you will find , The palms of both hands are still facing us , But the stacking order of hands has changed .

// Using three inversions to realize cyclic shift 
public class CircleGo_1 {
    

	public static void reverse(int nums[],int a, int b) {
    
		int middle;
		// Note the reversal , It is the inversion from the first to the last number of the interval , The middle number does not change 
		for(int i=0;i<(b-a+1)/2;i++) {
    
			middle=nums[a+i];
			nums[a+i]=nums[b-i];
			nums[b-i]=middle;
		}
	}
	public static void main(String[] args) {
    
		int nums[]= {
    1,2,3,4,5};
		int p =3,n=nums.length;
		reverse( nums, 0,p-1);
		reverse(nums, p,n-1);
		reverse(nums,0,n-1);
		System.out.println(Arrays.toString(nums));
	}
}

Permutation loop algorithm :

In ordinary circular transposition algorithm , Need to move a few steps , It needs to be cycled several times , Move one step at a time , Such spatial complexity is O(1), The time complexity is O(nk). If k Less than n, be O(n^2).
that , Is it possible to directly move the number to be moved to the position after the cycle , such , Each number only needs to be moved once to complete the cyclic shift , So if possible , How to determine the specific location to move .
For example, the sequence subscript is [i] Number of numbers , Its cyclic shift k Step , Then it should be in [i+k] The location of ,[i+k] The number of positions should be [i+2k] The location of , Because each element moves to the right n After that, he returned to his original position , So move right k Bit equals shift right k mod n position . So there is such a sequence of positions ：0,k,2k,…,(t-1)k. Each of them is in the mold n Position in the sense of .tk mod n The result is 0.t Is making tk mod n As the result of the 0 The smallest positive integer of . And t Is inevitable , The biggest is in t be equal to n When , In this way, a ring is formed .
To be exact, it forms a cyclic group .

This sequence of positions is essentially a module n The additive group consists of elements k Generate a cyclic subgroup . From the conclusion of group theory ( The proof of this conclusion is shown at the end ) know , Cyclic subgroup (k) The period of is n / gcd(k,n), The number of elements is n / gcd(k,n), The number of cosets is gcd(k,n). let me put it another way ,A[0…n-1] Cycle moves to the right k The result of bit is cyclic subgroup (k) And all its coset cycles are shifted one bit to the right . for example , take A[0…5] = {1,2,3,4,5,6} Cycle moves to the right 4 position , here n = 6, k = 4, gcd(k, n) = 2.A[0] The final position is 4,A[4] The final position is 2,A[2] The final position is 0, such , Location 0,4,2 It is from k=4 Generated cyclic group , The period is 6 / gcd(4,6) = 6 / 2 = 3, Such cyclic subgroups share gcd(4,6) = 2 individual .

So the complete code has , Make sure the gcd(k,n) Number of cyclic subgroups , Then shift the elements in the cyclic group one by one .

//  Cyclic shift of array 
#include <cstdio>

//gcd(x,y) Express x and y Maximum common factor of -- Euclidean algorithm 
int gcd(int m, int n) {
    
	int r;
	//r Record the remainder , Divide the divisor by the remainder , Until the remainder is 0, At this point, the divisor is the greatest common factor 
	while (r = m % n) {
    
		m = n; 
		n = r;
	}
	return n;
}

void shiftArray(int A[], int n, int k) {
    
	//  Because the code shifted to the left is much easier to implement than the code shifted to the right , And move right k position 
	//  Equivalent to moving left -k position , Generally speaking, shift right k position , Equal to shift left n-k position . The following code is moved left n-k Bit to shift right k position 
	k = n - (k % n);
	for (int i = 0, cnt = gcd(n, k); i < cnt; i++) {
    
		int t = A[i], p = i, j = (k + i) % n;
		while (j != i) {
    
			A[p] = A[j]; p = j; j = (k + p) % n;  
		}
		A[p] = t;
	}
}

void printArray(int A[], int n) {
    
	for (int i = 0; i < n; i++) {
    
		printf("%-3d", A[i]);
	
	}
}
int main() {
    
	int A[] = {
     1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
	printf(" Cycle to the right 12 Step \n");
	shiftArray(A, 15, 12);
	printArray(A, 15);
	return 0;
}