java - 在Java中使用递归来打印长度为N的位字符串的排列

我正在尝试获取表示长度为N的位字符串的可能排列的整数数组的链表，例如对于N = 2

00
01
10
11

我成功地编写了将位表示为字符串的代码，如下所示:

public static LinkedList<String> printBin(String soFar, int iterations) {
    if(iterations == 0) {
        LinkedList<String> ret = new LinkedList<String>();
        ret.add(soFar);
        return ret;
    }else {
        LinkedList<String> ret = new LinkedList<String>();
        ret.addAll(printBin(soFar + "0", iterations - 1));
        ret.addAll(printBin(soFar + "1", iterations - 1));
        return ret;
    }
}

但是我试图将这段代码转换为整数数组，因此N = 2

11 11 11 11

SSCE如下:

public class Main {
    public static void main(String[] args){
        int numberOfBits = 2;
        LinkedList<int []> results = printBin(new int[numberOfBits], 0, numberOfBits);
        Iterator<int[]> i = results.iterator();
        while(i.hasNext()){
            int[] temp = i.next();
            for(int j = 0; j < temp.length; j++){
                System.out.print(temp[j]);
            }
            System.out.println("");
        }
    }


    public static LinkedList<int[]> printBin(int[] soFar, int counter, int iterations) {
        if(iterations == 0) {
            LinkedList<int[]> ret = new LinkedList<int[]>();
            ret.add(soFar);
            return ret;
        }else {
            LinkedList<int[]> ret = new LinkedList<int[]>();
            int[] soFar1 = soFar; soFar1[counter] = 0;
            int[] soFar2 = soFar; soFar2[counter] = 1;
            ret.addAll(printBin(soFar1, counter + 1, iterations - 1));
            ret.addAll(printBin(soFar2, counter + 1, iterations - 1));
            return ret;
    }
}

}

任何帮助将不胜感激。

最佳答案

您的代码的问题在于，它在每个调用级别上一直重复使用数组soFar的相同实例，而不是进行复制。如果将代码更改为

int[] soFar1 = (int[])soFar.clone(); soFar1[counter] = 0;
int[] soFar2 = (int[])soFar.clone(); soFar2[counter] = 1;

您的代码应产生所需的结果(demo on ideone)。

但是，最好将所有整数从0迭代到(1 << numberOfBits) - 1并打印其二进制表示形式:

LinkedList<int[]> ret = new LinkedList<int[]>();
int endMask = 1 << numberOfBits;
for (int mask = 0 ; mask != endMask ; mask++) {
    int[] combo = new int[numberOfBits];
    for (int i = 0 ; i != numberOfBits ; i++) {
        combo[i] = ((mask & (1 << i)) != 0) ? 1 : 0;
    }
    ret.add(combo);
}

这是一个demo of iterative method on ideone。