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

Question

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

У меня есть этот код, который генерирует набор мощности из массива размером 4 (число является лишь примером, меньше комбинаций для записи …).

#define ARRAY_SIZE 4unsigned 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}

Так что заказывать надо так. Я не могу сделать это упорядочение после того, как этот алгоритм закончится, я должен использовать каждую комбинацию в каждой итерации, поэтому он должен генерировать уже упорядоченные комбинации. Кто-нибудь может мне помочь? Я думаю, что я думал обо всем …

РЕДАКТИРОВАТЬ: этот окончательный вывод должен быть без пустого набора, но это не приоритет.

15

algorithm bit-manipulation c++powerset subset

Решение

Другие решения

Напишите функцию для генерации всех элементов фиксированного размера. Обратите внимание, что первый такой элемент — 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));
}
}

1

Используйте буферный массив, а затем сортируйте его, используя qsort ?

Я использовал i_max*5 массив элементов: 4 unsigned int для значений (0 означает пустое, от 1 до 4 в противном случае) и окончательное целое число без знака для длины подмножества. Затем вам просто нужно свернуть с вашим пользовательским компаратором. Если вы хотите более упорядоченный алгоритм, взгляните на сортировку вставок: 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;
}

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

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

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

Увидеть Вот

0

Источник

Accepted Answer

Вот версия, которая сводится к металлу с небольшим переворотом. Он использует модифицированную версию знаменитого Восторг хакеров snoob() функция, которая генерирует следующее большее подмножество с Одинаковое количество битов. Увидеть Шахматное программирование вики (источник многих таких рутинных операций с битами).

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

9