15

我有这个代码，它生成一个大小为 4 的数组的幂集（数字只是示例，要编写的组合更少......）。

#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}

我需要那个输出是这样的：

{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}

所以必须这样订购。我不能在算法结束后进行排序，我必须在每次迭代中使用每个组合，所以它必须生成已经排序的组合。有人可以帮我吗？我想我什么都想好了……

编辑：最终输出应该没有空集，但这不是优先级。

4

5 回答 5

9

这是一个通过比特旋转深入到金属的版本。它使用著名的Hackers' Delightsnoob()函数的修改版本，该函数生成具有相同位数的下一个更大的子集。请参阅Chess Programming Wiki（许多此类位旋转例程的来源）。

#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);    
}

以字典顺序输出的实时示例（奖励功能）

{ }
{ 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, }
于 2013-10-10T19:30:59.457 回答
1

编写一个函数来生成所有固定大小的项目。请注意，第一个这样的项目是 1,..,k，而最后一个是 (n-k+1),..,n。这很简单，您基本上必须重新实现基本计数：增加最后一个“数字”，直到达到 n。然后你重置为 1 并以同样的方式继续到它的左边。

然后让 k 从 1 (0) 运行到 n。

这是内部算法的一种建议。不过还是比较丑的。

void out(std::vector<int> const& item) {
  char del = '{';
  for (auto it = item.begin(); it != item.end(); ++it) {
    std::cout << del << *it;
    del = ',';
  }
  std::cout << "}\n";
}

bool ascending(std::vector<int> const& item) {
  int last = 0;
  for (auto it = item.begin(); it != item.end(); ++it) {
    if (*it <= last)
      return false;
    last = *it;
  }
  return true;
}

void allk(int k, int n) {
  std::vector<int> item;
  item.reserve(k+1);
  for (int i = 1; i <= k; i++)
    item.push_back(i);
  bool valid = true;
  while (valid) {
    out(item);
    do {
      valid = false;
      for (auto it = item.rbegin(); it != item.rend(); ++it) {
        if (*it == n) {
          *it = 1;
        } else {
          ++*it;
          valid = true;
          break;
        }
      }
    } while (valid && !ascending(item));
  }
}
于 2013-10-10T15:37:31.740 回答
1
  • 我从一个简单的递归置换生成器开始。
  • 添加了一个长度参数，当长度达到 0 时，无需进一步排列，只需打印我们目前拥有的字符串。
  • 添加了我们必须继续从中挑选角色的位置。

编码：

（我知道有些人不喜欢原始数组/指针，但是与漂亮的容器相比，这个问题更容易获得出色的性能）

void powerSet(char *arr, int arrLen, int pos, int startPos, int length)
{
   if (length == 0)
      printf("%.*s\n", pos, arr);
   else
      for (int i = startPos; i < arrLen; i++)
      {
         std::swap(arr[pos], arr[i]);
         powerSet(arr, arrLen, pos+1, i+1, length - 1);
         std::swap(arr[pos], arr[i]);
      }
}

和调用函数：

void powerSet(char *arr, int arrLen)
{
    for (int i = 1; i <= arrLen; i++)
      powerSet(arr, 4, 0, 0, i);
}

powerSet("1234", 4)印刷：

1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234

测试。

于 2013-10-10T16:03:05.200 回答
1

使用缓冲区数组，然后使用qsort?

我使用了一个i_max*5元素数组：4unsigned int作为值（0 表示空，1 到 4 否则）和一个最终的 unsigned int 作为子集长度。然后，您只需要使用自定义比较器即可。如果您想要更精简的算法，请查看插入排序：http ://en.wikipedia.org/wiki/Insertion_sort

输出：

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,

Sorting
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,

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int comp (const void * elem1, const void * elem2) {
    unsigned int *f = (unsigned int*)elem1;
    unsigned int *s = (unsigned int*)elem2;
    unsigned int i;


    //printf("%d,%d,%d,%d,%d\n", f[0],f[1],f[2],f[3],f[4]);
    //printf("%d,%d,%d,%d,%d\n", s[0],s[1],s[2],s[3],s[4]);
    printf("\n");

    // Size comparison     
    if( f[4] > s[4] ) return 1;
    if( f[4] < s[4] ) return -1;

    // Value comparison
    for ( i = 0; i < 4; i++)
    {
        if (f[i] > s[i]) return  1;
        if (f[i] < s[i]) return -1;
    }

    return 0;
}

int main(int argc, char *argv[])
{
    unsigned int i, j, bits, i_max = (1U << 4);
    unsigned int *array;
    unsigned int index;

    array = calloc( 5*i_max, sizeof(unsigned int));

    // Non-sorted array
    for (i = 0; i < i_max ; ++i) {

        // Zero init for array
        memset(array + i*5, 0, 5*sizeof(*array));
        index = 0;

        for (bits = i, j = 0; bits; bits >>= 1, ++j) {

        if (bits & 1)
            {
                // Storage
                array[i*5 + index]   = j+1;

                index = (index + 1) % 4; // avoid buffer overflows
                array[i*5 + 4]   = array[i*5 + 4] + 1 ; // increment subset length

                //printf("%d,", array[i*5 + index - 1]);
            }
        }
        printf("\n");
    }

    // Print original array, without the zeros
    for (i =0; i < i_max; i++)
    {
        for(j = 0; j < 4 ; j++)
        {
            if( array[i*5 + j] )
                printf("%d,", array[i*5 + j]);
        }
        printf("\n");
    }


    printf ("Sorting\n");

    qsort (array, i_max, 5*sizeof(unsigned int), comp);


    // Print the sorted array, without the zeros
    for (i =0; i < i_max; i++)
    {
        for(j = 0; j < 4 ; j++)
        {
            if( array[i*5 + j] )
                printf("%d,", array[i*5 + j]);
        }
        printf("\n");
    }
    free(array);

    return 0;
}
于 2013-10-10T16:10:37.527 回答
0

我用这个答案制作了以下代码：

基本上你需要nCr为所有人打印序列r

#include <iostream>
#include <vector>

using namespace std;

 //This generates all nCr sequences
void display(const std::vector<int> & v, 
             std::vector<int>& comb, 
             int offset, int k) {
    if (k == 0) {
        std::cout<<"{";
        for(auto &x:comb)
            std::cout<<x<<",";
         std::cout<<"\b}"<<std::endl;
    return;
    }
    for (int i = offset; i <= v.size() - k; ++i) {
        comb.push_back(v[i]);
        display(v,comb,i+1, k-1);
        comb.pop_back();
    }
}

int main() {
    int n = 4;

     std::vector<int> v,comb;
    for (int i = 0; i < n; ++i) 
     v.push_back(i+1); 

    for (int i = 1; i <= n; ++i) 
        display(v,comb,0, i);

    return 0;
}

看这里

于 2013-10-10T16:58:38.337 回答