public class NextPermutationTest {
    
    public static void main(String[] args) {
        int[] arr = {10, 5, 3, 7};

        Arrays.sort(arr);     // 오름차순 정렬(사전순으로 가장 작은 순열)

        // 위에서 오름차순으로 정렬한 상태가 순열의 한 경우의 수이므로 순열을 이용하는 작업 수행 후 순열 만들기 진행
        do {
            System.out.println(Arrays.toString(arr));
        } while (nextPerm(arr));

    }

    // next permutation 메서드
    private static boolean nextPerm(int[] arr) {
        // 꼭대기 이전의 원소 구하기
        int biggest = arr.length-1;
        while (biggest>0 && arr[biggest-1] >= arr[biggest]) biggest--;

        // 꼭대기 원소가 배열의 첫번째라면 이미 모두 정렬된 순열이므로 false 반환
        if (biggest == 0) return false;

        // 꼭대기 이전 원소와 교환할 원소 찾기. 꼭대기 이후 원소들 중 꼭대기 이전 원소보다 크되, 가장 작은 원소 찾기
        int swapTarget = arr.length-1;
        while (arr[biggest-1] >= arr[swapTarget]) swapTarget--;

        // 위에서 찾은 두 원소 교환
        swap(arr, biggest-1, swapTarget);

        // 꼭대기부터 마지막 인덱스까지의 원소는 다시 오름차순 정렬
        int smallest = arr.length-1;
        while (smallest > biggest) {
            swap(arr, biggest++, smallest--);
        }

        return true;
    }

    // 원소 2개 교환 메서드
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

public class NextPermCombiTest {
    
    public static void main(String[] args) {
        int[] arr = {10, 5, 3, 7};
        int N = arr.length, R = 3;     // 배열 원소 중 R개 만큼 뽑음
        int[] combi = new int[N];      // 선택할 원소 체크 배열

        for (int i=N-1; i>=N-R; i--) combi[i] = 1;     // 선택할 원소 조합(N개 중 R개만 체크)을 오름차순으로 초기화

        // 위에서 오름차순으로 정렬한 상태가 조합의 한 경우의 수이므로 조합을 이용하는 작업 수행 후 조합 만들기 진행
        do {
            // 선택된 경우를 바탕으로 조합 구성
            for (int i=0; i<N; i++){
                if (combi[i] == 1) System.out.print(arr[i] + " ");
            }
            System.out.println();
        } while (nextPerm(combi));

    }

    // 순열 코드인 아래 코드는 수정하지 않아도 조합 구성 가능!
    // next permutation 메서드
    private static boolean nextPerm(int[] arr) {
        // 꼭대기 이전의 원소 구하기
        int biggest = arr.length-1;
        while (biggest>0 && arr[biggest-1] >= arr[biggest]) biggest--;

        // 꼭대기 원소가 배열의 첫번째라면 이미 모두 정렬된 순열이므로 false 반환
        if (biggest == 0) return false;

        // 꼭대기 이전 원소와 교환할 원소 찾기. 꼭대기 이후 원소들 중 꼭대기 이전 원소보다 크되, 가장 작은 원소 찾기
        int swapTarget = arr.length-1;
        while (arr[biggest-1] >= arr[swapTarget]) swapTarget--;

        // 위에서 찾은 두 원소 교환
        swap(arr, biggest-1, swapTarget);

        // 꼭대기부터 마지막 인덱스까지의 원소는 다시 오름차순 정렬
        int smallest = arr.length-1;
        while (smallest > biggest) {
            swap(arr, biggest++, smallest--);
        }

        return true;
    }

    // 원소 2개 교환 메서드
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}