[JAVA] 전체 값을 나열하는 순열 코드

 

list 에서 임의의 n개 값을 뽑아 나열하는 것을 순열이라고 한다.

 

순열 = 배열의 값들을 순서대로 나열하는 방법의 수.
nPr 이라고 표현.
nPn 은 n! 개
nPr 은 n!/(n-r)! 개 가 있다.

 

1,2,3 의 배열이 있고 이 때 3P3 은 3! = 6개
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
이렇게 나옴.

1,2,3 의 배열이 있고 이 때 3P2 는 3!/(3-2)! = 6개
1,2
1,3
2,1
2,3
3,1
3,3
이렇게 나옴.

 

 

아래 swap function 을 이용하여 list 전체의 값을 나열하는 방법을 소개한다.

 

*결과로 나온 값은 사전순이 아님

 

public class Main {
	private static int[] origin;
	public static void main(String[] args) throws Exception {
		
		int[] list = {0,1,2};
		permutation(list, 0);
	}
	
	private static void permutation(int[] list, int index) {
		if(index>=list.length) {
			System.out.println(Arrays.toString(list));
			return;
		}
		for(int i = index; i<list.length; i++) {
			swap(index, i, list);
			permutation(list, index+1);
			swap(index, i ,list);
		}
	}
    
	private static void swap(int a, int b, int[] list) {
		int temp = list[a];
		list[a]=list[b];
		list[b]=temp;
	}
}

 

input : {0,1,2}

결과 값 : 

[0, 1, 2]

[0, 2, 1]

[1, 0, 2]

[1, 2, 0]

[2, 1, 0]

[2, 0, 1]

 

input : {0,2,3,5}

결과 값 :

[0, 2, 3, 5]

[0, 2, 5, 3]

[0, 3, 2, 5]

[0, 3, 5, 2]

[0, 5, 3, 2]

[0, 5, 2, 3]

[2, 0, 3, 5]

[2, 0, 5, 3]

[2, 3, 0, 5]

[2, 3, 5, 0]

[2, 5, 3, 0]

[2, 5, 0, 3]

[3, 2, 0, 5]

[3, 2, 5, 0]

[3, 0, 2, 5]

[3, 0, 5, 2]

[3, 5, 0, 2]

[3, 5, 2, 0]

[5, 2, 3, 0]

[5, 2, 0, 3]

[5, 3, 2, 0]

[5, 3, 0, 2]

[5, 0, 3, 2]

[5, 0, 2, 3]

 

 

 

아래는 중복을 포함하여 나열하는 방법

public class Main {
    public static void main(String[] args) throws Exception {

        int[] nums = {0,1};
        Vector<int[]> list = new Vector<>();
        Stack<Integer> stack = new Stack<>();
        func(list, stack, nums);
        for(int[] l : list) {
            for(int i : l){
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }

    private static void func(Vector<int[]> list, Stack<Integer> stack, int[] nums){
        if(stack.size()==nums.length) {
            int[] temp = new int[nums.length];
            int i = 0;
            for(int s : stack) temp[i++]=s;
            list.add(temp);
            return;
        }
        for(int i=0; i<nums.length; i++){
            stack.add(nums[i]);
            func(list, stack, nums);
            stack.pop();
        }
    }
}

 

input : {0,1}

결과 값 :

[ 0 0 ]
[ 0 1 ]
[ 1 0 ]
[ 1 1 ]

 

input : {0,1,2}

결과 값 :

[ 0 0 0 ]
[ 0 0 1 ]
[ 0 0 2 ]
[ 0 1 0 ]
[ 0 1 1 ]
[ 0 1 2 ]
[ 0 2 0 ]
[ 0 2 1 ]
[ 0 2 2 ]
[ 1 0 0 ]
[ 1 0 1 ]
[ 1 0 2 ]
[ 1 1 0 ]
[ 1 1 1 ]
[ 1 1 2 ]
[ 1 2 0 ]
[ 1 2 1 ]
[ 1 2 2 ]
[ 2 0 0 ]
[ 2 0 1 ]
[ 2 0 2 ]
[ 2 1 0 ]
[ 2 1 1 ]
[ 2 1 2 ]
[ 2 2 0 ]
[ 2 2 1 ]
[ 2 2 2 ]

 

 

배열에서 모든 부분 집합들(Power Set) 을 다음과 같이 구할 수 있음

public class Main {
    public static void main(String[] args) throws Exception {
        int nums[] = {1,2,3};
        List<Integer> list = new Vector<>();
        func(nums, list, 0);
    }

    static void func(int[] nums,List<Integer> list, int index){
        for(int i : list) System.out.print(i+" ");
        System.out.println();
        for(int i=index; i<nums.length; i++){
            list.add(nums[i]);
            func(nums, list, i+1);
            list.remove(list.size()-1);
        }
    }
}

 

 

input : {1,2,3}

결과 값 :

[ ]
[ 1 ]
[ 1 2 ]
[ 1 2 3 ]
[ 1 3 ]
[ 2 ]
[ 2 3 ]
[ 3 ]

 

 

input : {1,2,3,4}

결과 값 :

[ ]
[ 1 ]
[ 1 2 ]
[ 1 2 3 ]
[ 1 2 3 4 ]
[ 1 2 4 ]
[ 1 3 ]
[ 1 3 4 ]
[ 1 4 ]
[ 2 ]
[ 2 3 ]
[ 2 3 4 ]
[ 2 4 ]
[ 3 ]
[ 3 4 ]
[ 4 ]