[순열, 조합] NextPermutation

- 현 순열에서 사전 순으로 다음 순열 생성

- 자바는 네퍼의 API가 없으므로 직접 구현해야함..

- 네퍼로 순열을 생성하는 것을 응용하여 조합을 할 수 있다.

- 주의 : 네퍼 하기 전 오름차순 정렬 후, 가장 작은 순열을 먼저 처리 해야한다.

순열

package com.ssafy.w0812.permutation;

import java.util.Arrays;

public class NextPermutationTest {

	public static void main(String[] args) {

		int[] input = {7,1,4};
		
		Arrays.sort(input); // 가장 작은 순열 만들기 , 1,4,7
		
		do {
			// 순열 사용
			System.out.println(Arrays.toString(input));
			
		}while(np(input));
	}
	
	// 다음 큰 순열이 있으면 true, 없으면  false
	private static boolean np(int[] numbers) {
		
		int N = numbers.length;
		
		// step1. 꼭대기(i)를 찾는다. 꼭대기를 통해 교환위치(i-1) 찾기
		int i = N-1;
		while(i>0 && numbers[i-1]>=numbers[i]) --i;
		
		if(i==0) return false;
		
		// step2. i-1 위치값과 교환할 큰 값 찾기
		int j = N-1;		
		while(numbers[i-1]>=numbers[j]) --j;
		
		// step3. i-1위치값과 j위치값 교환 
		swap(numbers,i-1,j);
		
		// step4. 꼭대기(i)부터 맨뒤 까지 내림차순형태의 순열을 오름차순으로 처리
		int k = N-1;
		while(i<k) {
			swap(numbers,i++,k--);
		}
		
		return true;
	}
	
	private static void swap(int[] numbers,int i,int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
	

}

1 4 7

1 7 4

4 1 7

4 7 1

7 1 4

7 4 1

조합

package com.ssafy.w0812.combination;

public class CombNextPermutationTest {

	public static void main(String[] args) {

		int[] input = {7,1,4,2,3};
		int N = input.length;
		int R = 4;
		
		int[] p = new int[N];
		// 뒤쪽부터 R개만큼 1채우기
		int cnt = 0;
		while(++cnt<=R) p[N-cnt] = 1;
		
		do {
			// 조합사용
			for (int i = 0; i < N; i++) {
				if(p[i]==1) System.out.print(input[i]+" ");
			}
			System.out.println();
		}while(np(p));
	}
	
	// 다음 큰 순열이 있으면 true, 없으면  false
	private static boolean np(int[] numbers) {
		
		int N = numbers.length;
		
		// step1. 꼭대기(i)를 찾는다. 꼭대기를 통해 교환위치(i-1) 찾기
		int i = N-1;
		while(i>0 && numbers[i-1]>=numbers[i]) --i;
		
		if(i==0) return false;
		
		// step2. i-1 위치값과 교환할 큰 값 찾기
		int j = N-1;		
		while(numbers[i-1]>=numbers[j]) --j;
		
		// step3. i-1위치값과 j위치값 교환 
		swap(numbers,i-1,j);
		
		// step4. 꼭대기(i)부터 맨뒤 까지 내림차순형태의 순열을 오름차순으로 처리
		int k = N-1;
		while(i<k) {
			swap(numbers,i++,k--);
		}
		
		return true;
	}
	
	private static void swap(int[] numbers,int i,int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}

}

1 4 2 3 
7 4 2 3 
7 1 2 3 
7 1 4 3 
7 1 4 2