java - 在 Java 中使用给定数量的 1 创建所有可能的二进制排列

Question

我想在 Java 中找到给定数量的所有可能的二进制排列:

• x 是每个序列中所需的 1 数量
• n 是每个序列所需的长度

举个例子:

x=2，n=4

输出:1100、0011、1010、1001、0101、0110

我正在寻找一种优雅而快速的方法来做到这一点。你能帮助我吗？我已经在 Print list of binary permutations 中测试了 eboix 解决方案但不幸的是它太慢了，因为这个例子中的算法正在搜索所有2^n二进制排列。我想查找长度为 50 或 100 的序列。

Answer 1

首先，您缺少 0110 作为输出案例。

很直观地知道有n 选择x 种可能性。您在总共 n 个槽位中找到了 x 个相同项目的所有有效排列。因此，您可以在 O(1) 中找到序列总数。

作为提示，尝试简单地查找由 x 个 1 和 n - x 零组成的位串的所有排列。

要专门解决该问题，请尝试创建一个递归算法，在每次迭代时决定包含 1 或 0。如果包含 1，则需要减少可用于字符串其余部分的 1 的计数。