javascript - 0 和 1 的组合优化

Question

我正在研究解决这个问题的方法: 给定 0 和 1 的数量，生成包含 0 和 1 的所有可能组合的列表。

示例:如果我们有一个 1 和两个 0，算法将返回

 001
 010
 100

问题在于经典组合算法并未为此目的进行优化。 这是非优化组合算法将返回的结果:

001
001
010
010
100
100

如您所见，所有组合都重复了两次，因为 0 被解释为不同的元素。

如何在不重复组合的情况下使算法生成输入 0 和 1 的数量的可能组合列表？

PS : 这将在 Javascript 中使用

编辑: 已解决!使用@Batch 方法。

function combin(o, i)
{
    if (o == 0 && i > 0) 
    {
        for (var j = 0, s = ''; j < i; j++)
        {
            s += '1';
        }
        return [s];
    } 
    else if (i == 0 && o > 0)
    {
        for (var j = 0, s = ''; j < o; j++)
        {
            s += '0';
        }
        return [s];
    } 
    else if (i == 0 && 0 == o)
    {
        return [''];
    } 
    else if (i > 0 && o > 0)
    {
        var l = combin(o - 1, i);
        for (var j in l)
        {
            l[j] = '0' + l[j];
        }
        var k = combin(o, i-1);
        for (var j in k)
        {
            k[j] = '1' + k[j];
        }
        return l.concat(k);
    }
}

Answer 1

这是一种方法:从将全 0 放在前面的字符串开始。现在将最右边的 0 移动到末尾。然后，将最右边第二个 0 向右移动一位，将最后一个 0 放在它旁边。同样，将最右边的 0 移动到末尾。将最右边第二个0再右移一步，再把最右边的0放在它旁边，shift shift shift。移动最右边的两个 0 对后，开始移动最右边的第三个 0...。您明白了。

示例:三个 0，三个 1:

000111
001011
001101
001110
010011
010101
010110
011001
011010
011100
100011
100101
100110
101001
101010
101100
110001
110010
110100
111000

不确定如何为此编写一个漂亮的循环，但一旦你掌握了这个想法，你就可以尝试并尝试找出一个你喜欢的循环。也许你可以找到一个漂亮的递归，虽然现在想不出这个方法。

---

更优雅的方法如下:请注意，生成所有包含 n 0 和 m 1 的字符串的方法是:

字符串以 0 开头，追加从 n-1 0 和 m 1 生成字符串的所有组合，或者字符串以 1 开头并追加所有组合从 n 0 和 m-1 1 生成字符串。生成的字符串集是不相交的，所以一个简单的递归就可以了，不用担心字符串会被多次生成。如果您愿意，您也可以迭代地进行(为此遍历生成的字符串的长度，对于迭代 i，保留未使用 0、使用 1 个 0、...、使用 0 等的集合)

总而言之，递归似乎适合我。基本情况很简单:如果 n = 0，您唯一可以获得的字符串是 1^m，如果 m = 0，您唯一可以获得的字符串是 0^n(其中 ^ 表示重复)。

---

如果您想实现该递归以及(在某种程度上)测试它的方法，请注意您可以生成的字符串数是 n + m 选择 n = n + m 选择 m，因此计算您获得的字符串数量将提示您所做的是否按预期工作。不确定 javascript 是否提供对二项式系数的轻松访问。