[java] 配列から順列を求める方法

序論

Javaを用いたアルゴリズムの勉強をしているが、Javaは順列を求めるような便利なコードは用意されてないので、自分でそのコードを用意する必要性があった。よってそれを調べたのでメモ。

Code

Permutation

public class Permutation {

	static void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
		if (depth == r) {
			print(output, r);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visited[i] != true) {
				visited[i] = true;
				output[depth] = arr[i];
				permutation(arr, output, visited, depth + 1, n, r);
				visited[i] = false;
			}
		}
	}

	static void swap(int[] arr, int depth, int i) {
		int temp = arr[depth];
		arr[depth] = arr[i];
		arr[i] = temp;
	}

	static void print(int[] arr, int r) {
		for (int i = 0; i < r; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}

public class PermutationUse {
	public static void main(String[] args) {
		int n = 3;
		int[] arr = { 1, 2, 3 };
		int[] output = new int[n];
		boolean[] visited = new boolean[n];

		Permutation.permutation(arr, output, visited, 0, n, n);
	}
}

Terminal

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

最初に並べた通りの順列を求めることができる。
sortをしておくと、辞書的な順番の結果を得ることができると思う。

出典