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

Question

我正在尝试获取一个整数数组的链表，表示长度为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;
    }
}

任何帮助都将不胜感激。

- John Walker

Answer 1

您不能这样做

    int[] soFar1 = soFar; soFar1[counter] = 0;
    int[] soFar2 = soFar; soFar2[counter] = 1;

这将导致 sofar1 和 sofar2 指向同一个数组。您需要创建一个新的数组并将内容复制到其中。

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

- Markus Mikkolainen

Answer 2

您的代码问题在于每个调用级别都会重复使用相同的数组实例soFar，而不是制作一个副本。如果您更改代码为

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

你的代码应该产生你想要的结果 (在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);
}

这里有一个迭代方法的演示，可以在ideone上查看： http://ideone.com/w9kTHs。

- Sergey Kalinichenko

---

但是迭代不会是递归=) - Markus Mikkolainen

@MarkusMikkolainen 递归？我们不需要任何该死的递归！(http://en.wikipedia.org/wiki/Stinking_badges) - Sergey Kalinichenko

Answer 3

建议：不要在参数中使用数组，而是从底向上处理返回值。

public static LinkedList<LinkedList<int>> printBin( int bits) {
    if(bits == 0) {
        LinkedList<LinkedList<int>> ret = new LinkedList<LinkedList<int>>();
        ret.add(new LinkedList<Int>());
        ret.get(0).add(0);
        ret.get(0).add(1);
        return ret;
    }else {
        LinkedList<LinkedList<int>> ret = printBin(bits-1);
        LinkedList<LinkedList<int>> ret2 = printBin(bits-1); // this should be deep copied
        for(LinkedList<int> bitstring : ret){
            bitstring.add(0); 
        }
        for(LinkedList<int> bitstring : ret2){
            bitstring.add(1); 
        }

        ret.addAll(ret2);
        return ret;
}

- dfb