incrementing/decrementing n位二进制递归（算法）

Question

我有一个家庭作业问题，我们应该想出一个递归算法来找到 n 位二进制数的七个排列，从 0 开始（例如，如果 n=4，则起始数是 0000 ).规则是想出尽可能小的数字变化，一次只改变 1 位，并获得尽可能小的十进制结果。

根据规则，第一个排列为0001（小数点1），第二个排列为0011（小数点3），第三个排列为0010，依此类推。我在问题中给出的排列是这些：
1. 0000 = 0
2. 0001 = 1
3. 0011 = 3
4. 0010 = 2
5. 0110 = 6
6. 0100 = 4
7. 0101 = 5

我知道并理解递归是如何工作的，但我只能做简单的（数字序列、阶乘、排列等），我不知道如何提出递归算法，可以有人帮忙吗？

Answer 1

你可以这样试试->

void rec(string s)
{
    mapped[s]=true;                 /// Mapping the string, which will stop repetition
    cout<<s<<endl;                  /// Printing s
    for(int i=0; i<4; i++){         /// looping through s
        if(!mapped[toggle(s,i)]){   /// checking if toggled string is mapped
            rec(toggle(s,i));       /// Calling the toggled string
        }
    }
}

此处，s=0000 & toggle 切换字符串 s 的 i-th 位。这是适合您的 toggle 函数 ->

string toggle(string s, int pos){
    if(s[pos]=='1')s[pos]='0';
    else s[pos]='1';
    return s;
}

代码块输出这个->

您可以在任何地方停止打印！！

Answer 2

如果你只想要 7 个最小的二进制字符串，我不太确定你所说的 "smallest decimal result possible" 是什么意思，因为你总是只有 0 - 110 但是如果出于某种原因你不想使用 C++ mapping:

public class f {
    static int count = 0;
    static int n = 7;// n smallest binary strings

    /**
     * 
     * @param str initialize with ""
     * @param len number of bits
     */
    static void g(String str,int len){
        if(count<n) {
            if (len == 0) {
                count++;
                System.out.println(str);
            } else {
                g(str + "0", len - 1);
                g(str + "1", len - 1);
            }
        }
    }

    public static void main(String[] args) {
        g("",4);
    }
}

incrementing/decrementing n位二进制递归（算法）

incrementing/decrementing n-bit binary by recursion (algorithm)

algorithm

recursion

permutation