순열

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
다수의 알고리즘 문제들은 순서화된 요소의 집합에서 최선의 방법을 찾는 것과 관련 있다.

최소 변경을 통해 순열을 만드는 방법

각각의 수열은 이전의 상태에서 단지 두 개의 요소 교환을 통해 생성된다!
👉 두 개를 자리바꿈 해서 순열을 만들 수 있음

비트마스킹을 통한 순열 생성

nums : 데이터
sel : 결과 저장 배열
visited : 해당 원소를 사용헀는지 체크

import java.util.Arrays;

public class 백트래킹_04_순열4 {
	public static int[] nums;// 배열
	public static int N; // 원소 수
	public static int[] result; // 결과 저장

	public static void main(String[] args) {
		nums = new int[] { 0, 1, 2 };
		N = nums.length;
		result = new int[N];
		perm(0, 0);
	}
	//idx 현재 내가 판단하는 위치
	public static void perm(int idx, int visited) {
//		if(visited == (1<<N)-1) //이 표현에 N개의 비트가 1로 가득차있는 상태이다.
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		//사용할 수 있는 모든 원소를 체크 하겠다.
		for(int i = 0 ; i< N; i++) {
			//해당 원소 썼니? 
			if((visited & (1<<i)) > 0) continue;
			result[idx] = nums[i]; //결과저장
			perm(idx+1, visited | (1<<i));
		}
		
	}
	
}

순열 구현

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//swap
public class 백트래킹_02_순열2 {
	public static int[] nums;// 배열
	public static int N; // 원소 수
	public static List<int[]> list;

	public static void main(String[] args) {
		nums = new int[] { 0, 1, 2 };
		N = nums.length;

		list = new ArrayList<>();

		perm(0);
		
		System.out.println(list.size());
		for(int[] a: list) {
			System.out.println(Arrays.toString(a));
		}
	}

	// idx : 현재 판단 위치
	public static void perm(int idx) {
		if (idx == N) {
			int[] tmp = new int[N];
			for(int i = 0 ; i<N; i++) {
				tmp[i] = nums[i];
			}
//			list.add(nums); 주소를 담아버리니 똑같은 것들이 계속 나오는거 같아 나중에 모아서 봤을떄.
			list.add(tmp);
//			System.out.println(Arrays.toString(nums));
			return;
		}

		// 재귀 조건
		for (int i = idx; i < N; i++) {
			swap(i, idx);
			perm(idx + 1);
			swap(i, idx);
		}

	}

	// nums 배열을 static 하게 해놓았기 때문에 인덱스만을 인자로 받아서 처리 가능
	public static void swap(int a, int b) {
		int tmp = nums[a];
		nums[a] = nums[b];
		nums[b] = tmp;

	}
}

static void perm(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];
            perm(arr, output, visited, depth + 1, n, r);       
            visited[i] = false;;
        }
    }
}