순열 vs 집합 vs 부분집합

순열

순열이란 ?
순서가 의미있는 조합이다. 즉, 순서가 달라지면 그 의미도 달라진다.

예를들어) 주사위를 3번 던졌을때 나올수있는 모든 수의 순서를 구하라
이경우에 (1,3,5)와 (3,1,5)는 다른 경우이다.

조합과 다르게 현재 선택된 수보다 작은수를 다음에 선택할수있다
-> visit배열을 이용하여 처리한다.

문제설명

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

내풀이

public class B10974 {
		static int[] arr;
		static int[] result;
		static boolean[] visited;
		static int n;
		
	public static void main(String[] args) throws IOException {
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		
		arr = new int[n];
		result= new int[n];
		visited = new boolean[n];
		
		for (int i = 0; i < n; i++) {
			arr[i]=i+1;	
		}
		
		recur(0);
	}

	private static void recur(int depth) {
		if(depth==n) {
			print();
			return;
		}
		for (int i = 0; i <n; i++) {
			if(visited[i]==false) {
			result[depth]=arr[i];
			visited[i] =true;
			recur(depth+1);	
			visited[i] =false;
			}}
		}
	
	private static void print() {
		for (int i : result) {
			System.out.print(i+" ");
		}
		System.out.println();
		
	}
}

조합

조합이란?
순서 상관없이 원소가 같으면 같은 결과로 취급한다.

예를들어) 동전 3개를 써서 600원을 만들어라 라고 한다면
그 조합으로 인한 결과값만 중요할뿐, 몇번째에 어느동전이 뽑혔는지는 중요하지 않다.
따라서 (500원, 50원, 50원)과 (50원, 50원, 500원)은 같은 결과로 취급한다.

그러므로 조합은 순열보다 경우의 수가 현저히 적다.

어떻게 구현할것인가?

조합은 보통 "앞만봐" 라고 표현한다.
앞에서부터 for문을 통해 완전탐색을 해왔다면 현재 index보다 전에 있는 index를 돌아볼 필요가 없다.

why? 현재 index보다 전에 있는 index는 이전에 탐색을 했을것이기 떄문이다.
또 순서가 의미가 없으므로 (1,3,5)와 (3,1,5)는 같은 결과로 취급하기 때문에
나보다 적은 index는 바라볼 필요가 없다.

문제설명

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

내풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class B2309 {
	static int n;
	static int[] arr;
	static int[] result;
	static boolean[] visited;
	static int count;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
		
		n=7;
		arr =new int[9];
		result= new int[n];
		visited= new boolean[arr.length];

		for (int i = 0; i < 9; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		recur(0,0);
	}

	private static void recur(int depth, int start) {
		
		if(depth==n) {
			int sum=0;
			for (int i = 0; i < n; i++) {
				sum = sum+result[i];
			}
			if(sum==100) {		
				print();
			}
			return;	
		}	
		for (int i = start; i <arr.length; i++) {
			if(visited[i]==false) {
				result[depth]=arr[i];
				visited[i]=true;
				recur(depth+1,i+1);
				if (count==1) return;
				visited[i]=false;		
			}	
		}	
	}
	private static void print() {
		count++;
		Arrays.sort(result);
		for (int i : result) {
			System.out.println(i);
			
		}		
	}
}

부분집합

부분집합이란?
부분집합이란 갯수의 제한이 없는 조합과 같다.
조합을 설명할때 3개 합이 ~ 이런조건이 있었으나 이제는 개수의 조건이 사라진것이다.

즉, 동전들로 어떻게든 합이 500원인 경우를 만들어봐 라고 했을때

(500), (100, 100, 100, 100, 100) ... 등 여러가지 경우가 나타날수 있다.

따라서 부분집합의 핵심은 개수의 제한이 없는것!!

public class 부분집합 {
	static int[] arr ; //원소
    static boolean[] visited;//사용여부
    static int n ; //답의 길이
    static int[] result; //답저장배열
    
    public static void main(String[] args) {
        arr = new int[]{1, 2, 3};
        n = 3;
        visited = new boolean[n];
//        powerSet(0);
        bit();
    }

    static void powerSet(int depth) { //부분집합
    								 // 1. 처음엔 visited가 다 false라 공집합
    								 // 2 . 2출력	
    								 // 3/  ftt ->depth(2) -> ftf ->depth(3) 2출력ㄱ 
        if (depth == n) {			// 0 {3} {2}  {
            printResult();
            return;
        }

        visited[depth] = false;
        powerSet(depth + 1);

        visited[depth] = true;
        powerSet(depth + 1);
    }

    static void bit() {
        for (int i = 0; i < 1 << n; i++) { //n이 3이면 i가 8보다 작을동안
            for (int j = 0; j < n; j++) { // j는 0부터 3까지
                if ((i & 1 << j) != 0) //i는 0000, j는0001 
                						//i는 0번째 추출할게 없다
                						// 0000 & 0010 이 0이 아니니간
                						// i는 1번째는 추출할게 없다 => i가0일땐 추출할게없다

                						//i=1,j=0 0001 추출할게잇다
                						//i=1,j=1 
                	                    // 즉 J는 0001,0010,0100,1000로 자리별로 1인지 검사
                				        // 여기서 i와 &연산을 했을 때 0이 아닐때만 출력함
                    System.out.print(arr[j] + " ");
            }
            System.out.println("");//공집합
        }
    }

    static void printResult() {
        for (int i = 0; i < n; i++) { 
            if (visited[i] == true)
                System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

result:

1
2
1 2
3
1 3
2 3