JAVA Combination 조합 코드 예제

코딩하다보면 combination으로 조합이 필요한 경우가 많다.

아래 코드를 이용해 array의 조합을 획득할 수 있다.

 

Combinatorics.java

package com.saltlux.shkim;

import java.math.BigInteger;

public class Combinatorics {
	int elements;
	int length;
	BigInteger totalResults, current;
	int[] indices;

	public Combinatorics(int elements) {
		this(elements, elements);
	}

	static final byte[] intToByteArray(int value) {
		return new byte[] { (byte) (value >>> 24), (byte) (value >>> 16), (byte) (value >>> 8), (byte) value };
	}

	static BigInteger factorial(int n) {
		BigInteger r = BigInteger.ONE;
		BigInteger ii = BigInteger.ONE;
		for (int i = 1; i <= n; i++) {
			r = r.multiply(ii);
			ii = ii.add(BigInteger.ONE);
		}
		return r;
	}

	void increase() {
		if (current.compareTo(totalResults) < 0)
			current = current.add(BigInteger.ONE);
	}

	int[] cloneIntArray(int[] org) {
		int[] tmp = new int[org.length];
		System.arraycopy(org, 0, tmp, 0, org.length);
		return tmp;
	}

	public Combinatorics(int elements, int length) {
		this.elements = elements;
		this.length = length;

		if (length == 0)
			totalResults = BigInteger.ZERO;
		else if (length == 1)
			totalResults = new BigInteger(intToByteArray(elements));
		else
			totalResults = factorial(elements).divide(factorial(length).multiply(factorial(elements - length)));

		rewind();
	}

	public void rewind() {
		current = BigInteger.ZERO;
		indices = new int[length];
		for (int i = 0; i < indices.length; i++)
			indices[i] = i;
	}


	public boolean hasMore() {
		return current.compareTo(totalResults) < 0;
	}

	public int[] next() {
		if (current.equals(BigInteger.ZERO)){
			increase();
			return cloneIntArray(indices);
		}
		if (current.equals(totalResults))
			return cloneIntArray(indices);
		for (int n = indices.length - 1; n >= 0; n--) {
			if (n == indices.length - 1 || indices[n + 1] == 0) {
				indices[n]++;

				for (int k = n + 1; k < indices.length; k++) {
					indices[k] = indices[k - 1] + 1;
				}
			}
			indices[n] = indices[n] % (elements - (indices.length - 1 - n));
		}
		increase();

		return cloneIntArray(indices);
	}
}

CombiTest.java

package com.saltlux.shkim;

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

import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

public class CombiTest{
	public static List<String> combiEntity(List<String> entities) {
		Combinatorics cn = new Combinatorics(entities.size(), 2);
		List<String> combiEntities = new ArrayList<String>();
		List<String> resultList = new ArrayList<String>();

		while (cn.hasMore()) {
			int[] combiEntity = cn.next();
			int sbjIdx = combiEntity[1];
			int objIdx = combiEntity[0];

			combiEntities.add(entities.get(sbjIdx) + ":-:" + entities.get(objIdx));
			combiEntities.add(entities.get(objIdx) + ":-:" + entities.get(sbjIdx));
		}
		resultList = Lists.newArrayList(Sets.newHashSet(combiEntities));

		return resultList;
	}
	
	public static void main(String[] args) {
		List<String> words = new ArrayList<String>();
		words.add("이순신");
		words.add("조선");
		words.add("거북선");
		words.add("장군");
		words.add("한산도_대첩");
		words.add("임진왜란");
		
		List<String> combiResults = new ArrayList<String>();
		combiResults = combiEntity(words);
		for(int i = 0; i < combiResults.size(); i++) {
			System.out.println(combiResults.get(i));
		}
	}
}

 

출력 결과

 

거북선:-:이순신
임진왜란:-:한산도_대첩
임진왜란:-:장군
장군:-:이순신
조선:-:한산도_대첩
거북선:-:임진왜란
한산도_대첩:-:이순신
임진왜란:-:이순신
이순신:-:거북선
임진왜란:-:조선
장군:-:조선
한산도_대첩:-:임진왜란
이순신:-:조선
한산도_대첩:-:장군
이순신:-:한산도_대첩
조선:-:임진왜란
이순신:-:장군
한산도_대첩:-:조선
장군:-:임진왜란
장군:-:거북선
조선:-:거북선
거북선:-:한산도_대첩
임진왜란:-:거북선
이순신:-:임진왜란
조선:-:장군
거북선:-:장군
한산도_대첩:-:거북선
조선:-:이순신
장군:-:한산도_대첩
거북선:-:조선

 

 

 

2개로 조합하는 것 뿐만 아니라 3개로 조합하는 것도 위 코드를 조금만 수정해서 가능하다 :-)