Hamming距离程序输出正确但顺序反转，求代码排查帮助

我正在编写一个名为Hamming的Java程序，需求是从命令行读取整数k和比特串s，计算Hamming距离（两个字符串中不同比特的数量），并输出所有与s的Hamming距离为k的比特串。

示例运行结果：

>java Hamming 2 0011
 1111 1001 1010 0101 0110 0000

我的当前代码：

public class Hamming{

public static void main(String[] args) {
    int k = Integer.parseInt(args[0]); // first argument, hamming distance

    String s = args[1]; // second argument, binary string

    // int array of binary bits that make up the binary string
    int[] bitsString = new int[s.length()];

    // genBinaryStrings(length of string, array of bits, iterating value, hamming distance, binary string)  
    genBinaryStrings(s.length(), bitsString, 0, k, s);
}


//Recursive function that prints all binary strings that are 'h' hamming distance from original
 
private static void genBinaryStrings(int numBits, int binString[], int i, int h, String givenBinString) {

    if (i == numBits) { // base case
        // convert array of bits into binary string of bits
        String currResult = "";
        for (int bit : binString) {
            currResult += Integer.toString(bit);
        }
        
        // check the hamming distance between the current result and the original string
        if (h == getHamDistance(currResult, givenBinString)) {
            System.out.print(currResult + " "); // valid hamming distance, print
        }
        return;
    }
    // generate next possible binary strings
    // generate binary string where next value = 0
    binString[i] = 0;
    genBinaryStrings(numBits, binString, i+1, h, givenBinString);

    // generate binary string where next value = 1
    binString[i] = 1;
    genBinaryStrings(numBits, binString, i+1, h, givenBinString);
}



// This method will Compute Hamming Distance between two binary string
private static int getHamDistance(String resultBinString, String givenBinString) {
    int hamDist = 0; // assume distance is 0 initially

    // iterate thru current resulting binary string
    for (int i = 0; i < resultBinString.length(); i++) {
        // check for differing bit values
        if (resultBinString.charAt(i) != givenBinString.charAt(i))
            hamDist++; // binary string is 1 more bit different
    }
    return hamDist; // total distance
}
}

但我的程序运行输出为：

>java Hamming 2 0011
 0000 0101 0110 1001 1010 1111

结果正确但顺序与示例相反，求帮忙排查问题。

问题原因与解决方法 #

问题出在递归生成二进制串的顺序上：你当前的代码是先设置当前位为0再递归，之后才设置为1递归，这会生成升序的二进制串序列；而示例要求的是降序输出，只需要调换这两步的顺序即可。

修改genBinaryStrings方法中的生成逻辑：

private static void genBinaryStrings(int numBits, int binString[], int i, int h, String givenBinString) {

    if (i == numBits) { // base case
        // convert array of bits into binary string of bits
        String currResult = "";
        for (int bit : binString) {
            currResult += Integer.toString(bit);
        }
        
        // check the hamming distance between the current result and the original string
        if (h == getHamDistance(currResult, givenBinString)) {
            System.out.print(currResult + " "); // valid hamming distance, print
        }
        return;
    }
    // 调换生成顺序：先1后0
    binString[i] = 1;
    genBinaryStrings(numBits, binString, i+1, h, givenBinString);

    binString[i] = 0;
    genBinaryStrings(numBits, binString, i+1, h, givenBinString);
}

修改后，程序会先生成高位为1的二进制串，输出顺序就会和示例完全一致。

内容的提问来源于stack exchange，提问作者Brian