memostack
article thumbnail
Published 2020. 2. 23. 22:48
Java 멱집합 구하기 (PowerSet) Algorithm
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
반응형

1. 멱집합 구하기

StackRecursive를 이용하여, 멱집합 (Power Set) 을 구한다.

 

{1, 2, 3} 집합의 부분 집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다. (공집합 포함)

2. Java 코드

2.1. 재귀함수 search()

search() 메소드를 생성한다.

<java />
private static void search(Stack<Integer> stack, int k) { if(k >= n + 1) { System.out.println(stack.toString()); // 부분 집합을 출력한다. } else { // k를 부분집합에 포함한다. stack.add(k); search(stack, k + 1); // k를 부분집합에 포함하지 않는다. stack.pop(); search(stack, k + 1); } }
  • 재귀를 돌리는데, k를 포함하는 경우와 포함하지 않는 경우, 2가지로 나눠서 수행한다.
  • k 가 주어진 n + 1 보다 커지는 경우 재귀를 멈춘다.
  • 그리고, stack에 들어있는 값들을 출력한다.

2.2. 전체 코드

<java />
import java.util.Stack; public class PowerSet { private static int n = 5; public static void main(String[] args) { final Stack<Integer> stack = new Stack<>(); search(stack, 1); } private static void search(Stack<Integer> stack, int k) { if(k >= n + 1) { System.out.println(stack.toString()); // 부분 집합을 출력한다. } else { // 1. k를 부분집합에 포함한다. stack.add(k); search(stack, k + 1); // 2. k를 부분집합에 포함하지 않는다. stack.pop(); search(stack, k + 1); } } }

 

2.3. 응용

주어진 문자들의 멱집합 구하기

<java />
package recursive; import java.util.Stack; public class PowerSet { private static final char[] characters = {'A', 'B', 'C', 'D', 'E'}; public static void main(String[] args) { final Stack<Character> stack = new Stack<>(); search(stack, 0); } private static void search(Stack<Character> stack, int k) { if(k >= characters.length) { System.out.println(stack.toString()); } else { stack.push(characters[k]); search(stack, k+1); stack.pop(); search(stack, k+1); } } }
반응형
블로그를 이전하였습니다. 2023년 11월부터 https://bluemiv.github.io/에서 블로그를 운영하려고 합니다. 앞으로 해당 블로그의 댓글은 읽지 못할 수 도 있으니 양해바랍니다.
profile

memostack

@bluemiv_mm

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!