按位移位生成 C 中所有可能的排列

发布于 2024-12-04 22:27:47 字数 587 浏览 2 评论 0原文

可能的重复：
创建具有一定位数设置的多个数字 < /p>

I我正在尝试编写一些代码，通过移位位将每个可能的数字组合放入一个数组中。

例如，我想找到 3 位的所有可能组合（其中最大数字可以是 6），数组应包含：

等等...

根据我的解释，当最后一个位置位为 1 时，我们将数字移动 1 (x >> 1) 并在开头添加 1。但是，我不确定如何编写其余的代码。我正在使用 C 来写这个。

另外 - 据我所知这是一个 colex 序列，但是，如果有另一个序列会给我相同的最终结果（具有 N 约束的所有可能的 k 位组合的数组），我会洗耳恭听。。

原文

Possible Duplicate:
Creating multiple numbers with certain number of bits set

I'm attempting to write some code which will put each possible combination of numbers in an array by shifting the bits across.

For example, I wanted to find all possible combinations of 3 bits (where the max a digit can be is 6) the array should contain:

And so on...

From what I've interpreted, when the last position bit is 1 we shift the number by 1 (x >> 1) and add a 1 at the start. However, I'm unsure how to code the rest. I'm using C to write this.

Also - as far as I can tell this is a colex sequence, however, I'm all ears if there is another sequence that will give me the same end result (array with all possible combinations of k-bits with a constraint of N).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

烟沫凡尘 2024-12-11 22:27:47

您可以通过递归生成序列来解决这个问题。

让我们定义一个递归函数f(int index, int bits, int number)，它将接受该位的当前index和bits< /code> 留在原处，以及到目前为止生成的 number。然后，您可以选择将当前位设置为 1 或 0，并从那里递归。

总的来说，时间复杂度应该是 O(序列数)，或 O(N 选择 B)，其中 N 是位数，B 是设置为 1 的位数。

该函数如下所示：

void f(int index, int bits, int number) {
    if (index == 0) {
        if (bits == 0) {   // all required bits have been used
            emit_answer(number); // chuck number into an array, print it, whatever.
        }   
        return;
    }   

    if (index-1 >= bits) {  // If we can afford to put a 0 here
        f(index-1, bits, number);
    }   

    if (bits > 0) {  // If we have any 1s left to place
        f(index-1, bits-1, number | (1 << (index-1)));
    }   
}

// to call:
f(6, 3, 0);

对于 N,B = 6,3 输出与您的匹配，并且按排序顺序排列。链接到工作示例：http://codepad.org/qgd689ZM

You can solve this by generating the sequences recursively.

Let us define a recursive function f(int index, int bits, int number) that will take in the current index of the bit and the number of bits left to place, and the number generated so far. Then, you have the option of setting the current bit to 1 or to 0, and recursing from there.

Overall, the time complexity should be O(number of sequences), or O(N choose B), where N is the number of digits and B is the number of bits set to 1.

The function goes something like this:

void f(int index, int bits, int number) {
    if (index == 0) {
        if (bits == 0) {   // all required bits have been used
            emit_answer(number); // chuck number into an array, print it, whatever.
        }   
        return;
    }   

    if (index-1 >= bits) {  // If we can afford to put a 0 here
        f(index-1, bits, number);
    }   

    if (bits > 0) {  // If we have any 1s left to place
        f(index-1, bits-1, number | (1 << (index-1)));
    }   
}

// to call:
f(6, 3, 0);

For N,B = 6,3 the output matches yours, and is in sorted order. Link to working example: http://codepad.org/qgd689ZM

回复收藏 0 原文

夜光 2024-12-11 22:27:47

可能有一种更有效的方法，但是您可以循环遍历数字并拒绝位数不为 3 的数字吗？请参阅此答案< /a> 用于位计数。

回复收藏 0 原文

清君侧 2024-12-11 22:27:47

不需要任何花哨的递归。一些简单的数学就足够了（需要除以一个始终是二的幂的值）。

    Function nextBits(ByVal prevVal As Integer)
        Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1
        Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal
        Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1)
        Return prevVal + lsOne + lowBits
    End Function

又好又容易。

No need for any fancy recursion. Some simple math will suffice (a division by a value which will always be a power of two is required).

    Function nextBits(ByVal prevVal As Integer)
        Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1
        Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal
        Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1)
        Return prevVal + lsOne + lowBits
    End Function

Nice and easy.

回复收藏 0 原文

~没有更多了~