순열(Permutation; 순서 O 중복 X)

순서 O 중복 X

 

서로 다른 것들 중 몇 개를 뽑아서 나열하는 것

 

https://www.acmicpc.net/problem/15649

import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] selected;
	static boolean[] used;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		selected = new int[m + 1];
		used = new boolean[n + 1];

		rec(1);

		sc.close();
	}

	private static void rec(int idx) {
		// 기저조건
		if (idx == m + 1) { //정해진 개수 다 뽑으면 출력
			for (int s = 1; s < selected.length; s++) {
				System.out.print(selected[s] + " ");
			}
			System.out.println();
			return; 
		}

		// 유도조건
		for (int i = 1; i <= n; i++) {
			if (used[i]) { //중복 없이 고르기 위함
				continue;
			}
			selected[idx] = i;
			used[i] = true; // 방문 처리
			rec(idx + 1); // 그 다음 수 뽑기
			used[i] = false; // 방문 처리 취소
		}
	}
}

 

 

참고. 중복 순열(순서 O 중복 O)

https://www.acmicpc.net/problem/15651

import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] arr;
	static StringBuilder sb;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		arr = new int[m + 1];
		sb = new StringBuilder();
		rec(1);
		System.out.println(sb.toString());
		sc.close();
	}

	private static void rec(int idx) {
		// 기저조건
		if (idx == m + 1) { // 개수에 맞게 다 뽑으면 종료
			for (int a = 1; a < arr.length; a++) {
				sb.append(arr[a]).append(" ");
			}
			sb.append("\n");
			return;
		}

		// 유도조건
		for (int i = 1; i <= n; i++) { // 뽑았는지 여부 중요치 않음
			arr[idx] = i;
			rec(idx + 1);
		}
	}
}