Johnson and Trotter

Kategori: Popular Algorithms , 17 Kasım 2019 , JanFranco


Problem:

Kullanıcıdan bir sayı aldığımızda, rakamların yerlerini değiştirerek yeni sayılar üreteceğiz. Örneğin 1234 girilirse 1243, 1342 gibi sayılar üreteceğiz.

Yaklaşım:

Johnson and Trotter algoritmasına göre aşağıdaki algoritma ile bu problemi çözebiliriz:

ALGORITHM JohnsonTrotter(n)

initialize the first permutation with 1<- 2<- .. n<-
while the last permutation has a mobile element do
    find its largest mobile element k
    swap k with the adjacent element k’s arrow points to
    reverse the direction of all the elements that are larger than k
    add the new permutation to the list

Bu çözüme göre aldığımız sayının tüm rakamlarının yönünü soldan sağa olarak belirleyeceğiz. Döngü yardımı ile her adımda yeni permütasyonlar elde edeceğiz. Döngünün kırılma koşulu son üretilen permütasyonun mobil sayıya sahip olup olmaması. Her adımda en büyük mobil sayıyı bulacağız. Bu sayıya k diyelim. k ile k'nın yönünün gösterdiği komşusunu yer değiştireceğiz. k'dan büyük bütün sayıların yönünü değiştireceğiz.

Çözüm:




public class JohnsonTrotter {
    
	private final static boolean LEFT_TO_RIGHT = true;
	private final static boolean RIGHT_TO_LEFT = false; 
	
	public static int factorial(int num) {
		int fact = 1;
		for(int i=1; i<=num; i++) {
			fact *= i;
		}
		return fact;
	}
	
	public static int getPos(int[] arr, int num) {
		for(int i=0; i<arr.length; i++) {
			if(arr[i] == num) {
				return i + 1;
			}
		}
		return 0;
	}
	
	public static int getMobile(int[] arr, boolean[] dir) {
		int mobile = 0, prevMobile = 0;
		for(int i=0; i<arr.length; i++) {
			if(dir[arr[i] - 1] == RIGHT_TO_LEFT && i != 0) {
				if(arr[i] > arr[i-1] && arr[i] > prevMobile) {
					mobile = arr[i];
					prevMobile = mobile;
				}
			}
			if(dir[arr[i] - 1] == LEFT_TO_RIGHT && i != arr.length - 1) {
				if(arr[i] > arr[i+1] && arr[i] > prevMobile) {
					mobile = arr[i];
					prevMobile = mobile;
				}
			}
		}
		if(mobile == 0 && prevMobile == 0) {
			return 0;
		}
		return mobile;
	}
	
	public static void printOnePerm(int[] arr, boolean[] dir) {
		int mobile = getMobile(arr, dir), pos = getPos(arr, mobile);
		
		if(dir[arr[pos - 1] - 1] == RIGHT_TO_LEFT) {
			int temp = arr[pos - 1]; 
            arr[pos - 1] = arr[pos - 2]; 
            arr[pos - 2] = temp; 
		}
		else if(dir[arr[pos - 1] - 1] == LEFT_TO_RIGHT) { 
            int temp = arr[pos]; 
            arr[pos] = arr[pos - 1]; 
            arr[pos - 1] = temp; 
        }
		for(int i=0; i<arr.length; i++) {
			if(arr[i] > mobile) { 
				dir[arr[i] - 1] = dir[arr[i] - 1] == LEFT_TO_RIGHT ? RIGHT_TO_LEFT : LEFT_TO_RIGHT;
            } 
		}
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]);
		} 
		
        System.out.print(" "); 
	}
	
	public static void printPerm(int n) {
		int[] arr = new int[n];
		boolean[] dir = new boolean[n];
		
		for(int i=0; i<n; i++) {
			arr[i] = i+1;
			dir[i] = RIGHT_TO_LEFT;
			System.out.print(arr[i]);
		}
		
		System.out.print("\n");
		
		for(int i=1; i<factorial(n); i++) {
			printOnePerm(arr, dir);
		}
		
	}
	
	public static void main(String[] args) {
		printPerm(4);
	}

}


Sonraki Yazı: Lexicographic Permute
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın