Lexicographic Permute

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


Problem:

Kullanıcının verdiği sayının basamaklarının yerini değiştirerek yeni sayılar üretmek istiyoruz. Örneğin 123 sayısı verildi. Bu durumda çıktımızda 123 132 213 231 312 321 sayılarını görmek istiyoruz.

Yaklaşım:

Lexicographic Permute algoritmasının sahte kodunu inceleyelim:

ALGORITHM LexicographicPermute(n)

initialize the first permutation with 12 . . . n
while last permutation has two consecutive elements in increasing order do
    let i be its largest index such that ai < ai+1
    find the largest index j such that ai < aj
    swap ai with aj
    reverse the order of the elements from ai+1 to an inclusive
    add the new permutation to the list

Bir döngü yardımı ile permütasyonları elde edeceğiz. Döngünün kırılması ardışık iki sayının olmamasına bağlı. Örneğin 123 sayısında 12 ve 23 ardışık sayılar. 321 sayısına baktığımızda burada ardışık sayı yok. Her adımda num[i] < num[i+1] koşulunu sağlayan maksimum i değerini ve num[i] < num[j] koşulunu sağlayan maksimum j sayısını bulacağız. Bu iki indeksi elde ettikten sonra bu indekse karşılık gelen sayıları yer değiştireceğiz. Daha sonra i+1. sayıdan başlayarak dizinin sonuna kadar olan kısmı ters çevireceğiz.

Çözüm:




public class LGPermute {
	
	public static int factorial(int num) {
		int fact = 1;
		for(int i=1; i<=num; i++) {
			fact *= i;
		}	
		return fact;
	}
	
	public static boolean checkConsecutive(int arr[]) {
		for(int i=0; i<arr.length-1; i++) {
			if(arr[i] < arr[i+1]) {
				return true;
			}
		}
		return false;
	}
	
	public static int getI(int arr[]) {
		int index = 0;
		for(int i=0; i<arr.length-1; i++) {
			if(arr[i] < arr[i+1] && i > index) {
				index = i;
			}
		}
		return index;
	}
	
	public static int getJ(int[] arr, int index) {
		for(int i=arr.length-1; i>index; i--) {
			if(arr[i] > arr[index]) {
				return i;
			}
		}
		return 0;
	}
	
	public static int[] swap(int[] arr, int i1, int i2) {
		int temp = arr[i1];
		arr[i1] = arr[i2];
		arr[i2] = temp;
		return arr;
	}
	
	public static int[] reverse(int[] arr, int start) {
		int j = arr.length-1, len = arr.length - start;
		for(int i=start; i<(len/2)+start; i++) {
			arr = swap(arr, i, j);
			j--;
		}
		return arr;
	}
	
	public static void printArr(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]);
		}
		System.out.print(" ");
	}
	
	public static void lexicographicPermutations(int range) {
		int[] arr = new int[range];
		for(int i=0; i<range; i++) {
			arr[i] = i + 1;
			System.out.print(arr[i]);
		}
		System.out.print("\n");
		while(checkConsecutive(arr)) {
			int i = getI(arr);
			int j = getJ(arr, i);
			arr = swap(arr, i, j);
			arr = reverse(arr, i+1);
			printArr(arr);
		}
	}
	
	public static void main(String[] args) {
		lexicographicPermutations(3);
	}

}

>>

123
132 213 231 312 321


Sonraki Yazı: Binary Reflected Gray Code
Yorumlar

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