发电机组由位产生 [英] Power set generated by bits

问题描述

我有此code产生大小4的阵列的功率设定（编号仅仅是例子，少的组合，以写...）。

I have this code which generates power set of an array of size 4 (number is just example, less combinations to write...).

#define ARRAY_SIZE 4


unsigned int i, j, bits, i_max = 1U << ARRAY_SIZE;
int array[ARRAY_SIZE];

for (i = 0; i < i_max ; ++i) {
    for (bits = i, j = 0; bits; bits >>= 1, ++j) {
        if (bits & 1)
            printf("%d", array[j]);
    }
}

输出：

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
{4}
{1, 4}
{2, 4}
{1, 2, 4}
{3, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

我需要输出的是像这样的：

I need that output to be like this one:

{1}
{2}
{3}
{4}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}
{1, 2, 3}
{1, 2, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, 4}

因此​​，必须订购这样的。我不能这样做排序的算法结束后，我必须用每一种组合的每次迭代，所以它产生的组合已经订购。有人可以帮我吗？我想，我在想一切......

So it has to be ordered like that. I can't do that ordering after that algorithm ends, I have to use every combination in every iteration, so It has to generate that combinations already ordered. Can someone help me out? I think I was thinking about everything...

编辑：那最后的输出应该没有空集，但它不是优先

That final output should be without empty set, but it's not priority.

推荐答案

下面是下降到与位变换的金属版本。它采用了著名黑客欢欣的）修改后的版本 snoob（ 函数生成下一个更大的子集在相同编号的一个位。请参阅<一href="http://chessprogramming.wikispaces.com/Traversing+Subsets+of+a+Set#Subsets%20with%20equal%20Cardinality-Snoobing%20any%20Sets">Chess编程维基（很多这样的位变换程序源）。

Here's a version that goes down to the metal with bit-twiddling. It uses a modified version of the famous Hackers' Delight snoob() function that generates the next greater subset with the Same Number Of One Bits. See the Chess Programming Wiki (a source of many such bit-twiddling routines).

#include <cstdint>
#include <iostream>

using U64 = uint64_t;

// print bit indices of x
void setPrint(U64 x)
{
    std::cout << "{ ";
    for(auto i = 1; x; x >>= 1, ++i)
        if (x & 1) std::cout << i << ", ";
    std::cout << "}\n";
}

// get next greater subset of set with 
// Same Number Of One Bits
U64 snoob (U64 sub, U64 set) {
   U64 tmp = sub-1;
   U64 rip = set & (tmp + (sub & (0-sub)) - set);
   for(sub = (tmp & sub) ^ rip; sub &= sub-1; rip ^= tmp, set ^= tmp)
       tmp = set & (0-set);
   return rip;
}

void generatePowerSet(unsigned n)
{
    auto set = (1ULL << n) - 1;                 // n bits
    for (unsigned i = 0; i < n+1; ++i) {
        auto sub = (1ULL << i) - 1;             // i bits
        U64 x = sub; U64 y; 
        do {            
            setPrint(x);
            y = snoob(x, set);                  // get next subset
            x = y;
        } while ((y > sub));
    }
}

int main()
{
    generatePowerSet(4);    
}

活生生的例子 在字典顺序输出（奖金特点）

Live Example with output in lexicographic order (bonus feature)

{ }
{ 1, }
{ 2, }
{ 3, }
{ 4, }
{ 1, 2, }
{ 1, 3, }
{ 2, 3, }
{ 1, 4, }
{ 2, 4, }
{ 3, 4, }
{ 1, 2, 3, }
{ 1, 2, 4, }
{ 1, 3, 4, }
{ 2, 3, 4, }
{ 1, 2, 3, 4, }

这篇关于发电机组由位产生的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！