Набор мощности, сгенерированный битами

Ответ 1

Здесь версия, которая идет вниз к металлу с бит-twiddling. Он использует модифицированную версию знаменитой функции Хакерса Delight snoob(), которая генерирует следующее большее подмножество с одним и тем же количеством битов. См. 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);    
}

Live Example с выходом в лексикографическом порядке (бонусная функция)

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

Ответ 2

Напишите функцию для создания всех элементов фиксированного размера. Обратите внимание, что первый такой элемент равен 1,..., k, а последний - (n-k + 1),..., n. Это очень просто, вам в основном нужно переопределить базовый подсчет: вы увеличиваете последнюю цифру, пока не достигнете n. Затем вы reset до 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));
  }
}

Ответ 3

Использовать массив буфера, а затем отсортировать его с помощью qsort?

Я использовал массив элементов i_max*5: 4 unsigned 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;
}

Ответ 4

• Я начал с простого рекурсивного генератора перестановок.
• Добавлен параметр длины и, когда длина достигает 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

Тест.

Ответ 5

Я использовал этот ответ, чтобы сделать следующий код:

В основном вам нужно печатать последовательности 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;
}

См. здесь