permutation - 生成两位数相等的所有排列

Question

在这里，我得到了两个数量相等的数字 1 和 0。现在我试图找到它的可能排列。像这样假设我给了 2 个 1 和 2 个 0。我从这个 0011 开始。然后我将第一个 1 沿左侧移动生成 0101 然后 1001。现在我移动第二个 1 生成 1010 和 1100。这种方法是否有效。我缺少 0110，我不知道该怎么做。我想有像递归回溯这样的方法来做到这一点。但我不知道回溯的技术。我确实了解递归。所以谁能告诉我方法吗？迭代或递归。如果可能，两者都可以。我试图找到所有可能的排列。对于 2 个 1 和 0，它是 1001,1100,1010,0101,0110,0011。这是 4!/(2!*2!) 排列。我该如何做更多，例如 111000 或 11110000 ？语言是 C++。为了澄清起见，它可以是任何字符，如 ooii 或 kkjj。那应该是我正在操作的字符串

Answer 1

用您喜欢的语言阅读一些排序算法。这里有一些排序类型的描述：

https://en.wikipedia.org/wiki/Sorting_algorithm

或者

我不知道你在说什么。

Answer 2

这听起来像是一个家庭作业问题（如果我错了，请纠正我），所以我将提供一些伪代码来说明一般方法。您必须弄清楚如何调整算法以在 C++ 中工作（并希望在此过程中理解它）。

这个想法是获取每个字符并将其递归地附加到剩余字符的每个排列中。基本情况是空字符串。

function foo (List<char> chars)
    List<string> permutations = new List<string>()
    for i:0..chars.length - 1
        List<string> subPermutations = foo(chars.removeAt(i))
        for each string perm in subPermutations
            permutations.add(chars.get(i) + perm)
        end for
    end for
    if permutations is empty
        permutations.add("")
    end if
    return permutations
end foo

作为补充说明，当您专门处理重复的 2 个不同字符时，这将为您提供很多重复的排列。您的选择是在将排列添加到列表之前检查是否已经生成了排列，最后从列表中删除重复项，或者针对您的情况优化递归。