Q7.1.1 한 그룹의 수의 조합을 모두 열거하다

제목:
하나의 수조 안의 수의 조합을 모두 열거합니다. 예를 들어 1과 2열은 1,2,12,21입니다.
분석:
이 문제는 여러 가지 확장이 있는데,
1, 중복된 원소의 수의 조합이 없다(자집의 전체 배열 포함).
2, 중복 원소의 수의 조합이 있다.
3, 중복 원소의 수가 없는 전체 배열;
4, 중복된 원소의 수의 전체 배열이 있다.
1, 중복된 원소의 수가 없는 조합
사고방식: 그룹 요소를 LinkedList에 저장하고 List를 훑어보며 현재 요소를 삭제하고 이 요소를 결과에 추가합니다. 결과 길이가 0이 되지 않으면 출력합니다.

package javainterview;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Q7_1_1_a {

	public static void listAll(List<Integer> candidate, String prefix){
		if(prefix.length()!=0){
			System.out.println(prefix);
		}
		
		
		for(int i=0; i<candidate.size(); i++){
			
			List<Integer> temp = new LinkedList<Integer>(candidate);
			int item = (int)temp.remove(i);
			listAll(temp, prefix+item);
		}
	}
	public static void main(String[] args) {
		
		Integer[] array = {1,2};
		List<Integer> list = Arrays.asList(array);
		listAll(list, "");
	}
}

2, 중복된 원소의 수가 있는 조합
사고방식은 중복 요소가 있기 때문에 1의 방법에 따라 중복 상황이 발생할 수 있다. 이곳의 처리 방법은 결과를 하나의 HashSet에 저장하고 결과를 얻을 때마다 HashSet에 이미 존재하고 존재하지 않는지 검사하여 출력하는 것이다.

package javainterview;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Q7_1_1_b {

	public static void listAll(List<Integer> candidate, String prefix, HashSet<String> hs){
		if(prefix.length()!=0 && !hs.contains(prefix)){
			System.out.println(prefix);
			hs.add(prefix);
		}
		
		
		for(int i=0; i<candidate.size(); i++){
			
			List<Integer> temp = new LinkedList<Integer>(candidate);
			int item = (int)temp.remove(i);
			listAll(temp, prefix+item, hs);
		}
	}
	public static void main(String[] args) {
		
		Integer[] array = {1,1,2};
		List<Integer> list = Arrays.asList(array);
		HashSet<String> hs = new HashSet<String>();
		listAll(list, "", hs);
	}
}

3, 중복 요소의 전체 정렬 없음
사고방식, 다른 점은 모든 원소의 전체 배열만 하면 자집을 하지 않는다는 것이다.그러면 출력할 때 판단을 하나 더 하면 됩니다.list의size는 0입니다.

package javainterview;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Q7_1_1_c {
	
	public static void listAll(List<Integer> candidate, String prefix){
		if(candidate.size()==0 && prefix.length()!=0){
			System.out.println(prefix);
		}
		
		
		for(int i=0; i<candidate.size(); i++){
			
			List<Integer> temp = new LinkedList<Integer>(candidate);
			int item = (int)temp.remove(i);
			listAll(temp, prefix+item);
		}
	}
	public static void main(String[] args) {
		
		Integer[] array = {1,2};
		List<Integer> list = Arrays.asList(array);
		listAll(list, "");
	}

}

편리를 위해 문자열 전체 배열이든 그룹 전체 배열이든 모두 LinkedList로 바꾸어 처리합니다

package javainterview;

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

public class Permutation {
	
	public static List<String> permutation(String s){
		List<String> res = new ArrayList<String>();
		if(s==null) return res;
		
		List<Character> list = new LinkedList<Character>();
		for(int i=0; i<s.length(); i++)
			list.add(s.charAt(i));
		permutation(res, list, "");
		return res;
		
	}
	public static void permutation(List<String> res, List<Character> list, String prefix){
		if(list.size()==0)
			res.add(prefix);
		for(int i=0; i<list.size(); i++){
			
			List<Character> temp = new LinkedList<Character>(list);
			char item = (char)temp.remove(i);
			permutation(res, temp, prefix+item);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "";
		List<String> res = permutation(s);
		for(String item : res)
			System.out.println(item + ";");
	}
}

4, 중복 요소의 전체 배열
사고방식: HashSet으로 결과를 저장합니다.

package javainterview;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Q7_1_1_d {
	
	public static void listAll(List<Integer> candidate, String prefix, HashSet<String> hs){
		if(candidate.size()==0 && prefix.length()!=0 && !hs.contains(prefix)){
			System.out.println(prefix);
			hs.add(prefix);
		}
		
		
		for(int i=0; i<candidate.size(); i++){
			
			List<Integer> temp = new LinkedList<Integer>(candidate);
			int item = (int)temp.remove(i);
			listAll(temp, prefix+item, hs);
		}
	}
	public static void main(String[] args) {
		
		Integer[] array = {1,1,2};
		List<Integer> list = Arrays.asList(array);
		HashSet<String> hs = new HashSet<String>();
		listAll(list, "", hs);
	}

}