프로그래밍을 하다 보면 바이너리 순열이 필요 할 때가 있다. 바이너리 순열은 단순히 00…00, 00…01, 00…10, 00…11같은 순열을 말한다. 예를 들어, 크기가 3인 바이너리 순열은 000,001,010,011,100,101,110,111이다. 아래는 바이너리 순열을 출력하는 java 코드이다.

기본적인 바이너리 순열

String[] initBinary(String[] arr,int N) {
    if (arr == null || N == 0 ) return null;

    for(int i = 0 ; i < arr.length; i++) {
        arr[i] = "";
        for (int k = 0 ; k < N ; k++)
            arr[i] += (i & (1<<k)) == (1<<k) ? "1" : "0";
    }
    return arr;
}

다른 버전으로는 boolean[ ][ ]을 리턴하는 버전도 있다.

void initBinary(boolean[][] caseCount) {
    if (caseCount.length == 0 || caseCount[0].length == 0) return;

    int cycle = caseCount[0].length;
    for(int i = 0 ; i < caseCount.length; i++) {
        for (int k = 0 ; k < cycle ; k++)
            caseCount[i][k] = (i & (1<<k)) == (1<<k) ? true : false;
    }
    return ;
}

변칙적인 바이너리 순열

변칙적인 바이너리 순열은 여러가지가 있는데, 일반적인 바이너리 순열에서 순서를 바꾼 것이다. 예를들어 1’s-ordered 바이너리 순열은 구성하고 있는 1의 개수에 따라 정렬된 순열을 말한다. 1의 개수가 적을 수록 앞에 위치하며, 1의 개수가 같다면 그 크기가 작은게 앞에 위치하게 된다. 예를들어 크기가 4인 1’s-ordered 바이너리 순열은 다음과 같다. 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111 이 일 것이다. 아래는 1’s-ordered 바이너리 순열 코드이다.

public class binaryCount implements Comparable<binaryCount>{
    int length;
    boolean[] caseArr;
    String str;
    int elementCount;
    int real;

    public binaryCount(boolean[] input) {
    	this.length = input.length;
    	this.caseArr = input;
    	this.real = 0; this.elementCount = 0; this.str = "";
    	for (int i = length-1 ; i >= 0 ; i -- ) {
    		if (input[i]) {
    			this.elementCount ++;
    			this.real += (int)Math.pow(2, i);
    			this.str += "1";
    		} else this.str += "0";
    	}
    }

    @Override
    public int compareTo(binaryCount target) {
    	if (this.elementCount > target.elementCount)
    		return 1;
    	else if (this.elementCount < target.elementCount)
    		return -1;
    	else {
    		if (this.real > target.real) return 1;
    		else if (this.real < target.real) return -1;
    		else return 0;
    	}
    }
}

다음은 이를 사용하기 위한 코드이다.

public class Main {
	  public static void main(String[] args) {
        int size = 4;
        int caseCount = (int) Math.pow(2,size);

        boolean[][] allCase = new boolean[caseCount][size];
        initBinary(allCase);

        ArrayList<binaryCount> caseList = new ArrayList<binaryCount>();
        for (int i = 0; i < testSet.length ; i++) {
        	caseList.add(new binaryCount(testSet[i]));
        }

        caseList.sort(Comparator.naturalOrder());

        // 출력
        for (int i = 0; i < caseList.size(); i ++ )
        	System.out.println(caseList.get(i).str + " : "+caseList.get(i).real);
        System.out.println("");
    }
}

아래와 같은 출력을 볼 수 있다.

0000 : 0
0001 : 1
0010 : 2
0100 : 4
1000 : 8
0011 : 3
0101 : 5
0110 : 6
1001 : 9
1010 : 10
1100 : 12
0111 : 7
1011 : 11
1101 : 13
1110 : 14
1111 : 15