Найти n-й набор powerset

У меня нет закрытой формы для функции, но у меня есть хакерский цикл next_combination функция, к которой вы можете обратиться, если это поможет. Предполагается, что вы можете поместить битовую маску в некоторый целочисленный тип, что, вероятно, не является необоснованным предположением, учитывая, что есть 2⁶⁴ возможности для набора из 64 элементов.

Как говорится в комментарии, я нахожу это определение «лексикографического упорядочения» несколько странным, поскольку я бы сказал, что лексикографическое упорядочение будет следующим: [], [a], [ab], [abc], [ac], [b], [bc], [c], Но раньше мне приходилось делать перечисление «сначала по размеру, потом по лексикографии».

// Generate bitmaps representing all subsets of a set of k elements,
// in order first by (ascending) subset size, and then lexicographically.
// The elements correspond to the bits in increasing magnitude (so the
// first element in lexicographic order corresponds to the 2^0 bit.)
//
// This function generates and returns the next bit-pattern, in circular order
// (so that if the iteration is finished, it returns 0).
//
template<typename UnsignedInteger>
UnsignedInteger next_combination(UnsignedInteger comb, UnsignedInteger mask) {
UnsignedInteger last_one = comb & -comb;
UnsignedInteger last_zero = (comb + last_one) &~ comb & mask;
if (last_zero) return comb + last_one + (last_zero / (last_one * 2)) - 1;
else if (last_one > 1) return mask / (last_one / 2);
else return ~comb & 1;
}

Строка 5 выполняет бит-хакерский эквивалент замены (расширенного) регулярного выражения, которая находит последний 01 в строке переворачивает 10 и сдвигает все следующие 1до упора вправо.

s/01(1*)(0*)$/10\2\1/

Строка 6 делает это (только если предыдущий не удался), чтобы добавить еще один 1 и сдвинуть 1до упора вправо:

s/(1*)0(0*)/\21\1/

Я не знаю, помогает ли это объяснение или мешает 🙂

Вот быстрый и грязный драйвер (аргумент командной строки — это размер набора, по умолчанию 5, максимальное количество битов в беззнаковых длинных):

#include <iostream>

template<typename UnsignedInteger>
std::ostream& show(std::ostream& out, UnsignedInteger comb) {
out << '[';
char a = 'a';
for (UnsignedInteger i = 1; comb; i *= 2, ++a) {
if (i & comb) {
out << a;
comb -= i;
}
}
return out << ']';
}

int main(int argc, char** argv) {
unsigned int n = 5;
if (argc > 1) n = atoi(argv[1]);
unsigned long mask = (1UL << n) - 1;
unsigned long comb = 0;
do {
show(std::cout, comb) << std::endl;
comb = next_combination(comb, mask);
} while (comb);
return 0;
}

Трудно поверить, что эта функция может быть полезна для набора из более чем 64 элементов, учитывая размер перечисления, но может быть полезно перечислить некоторую ограниченную часть, такую ​​как все подмножества трех элементов. В этом случае бит-хакерство действительно полезно, только если модификация помещается в одно слово. К счастью, это легко проверить; вам просто нужно выполнить вычисления, как указано выше, для последнего слова в наборе битов, вплоть до проверки на last_zero быть ноль. (В этом случае вам не нужно maskи, возможно, вы захотите выбрать другой способ задания заданного размера.) Если last_zero оказывается равным нулю (что на самом деле будет довольно редко), тогда вам нужно выполнить преобразование каким-то другим способом, но принцип тот же: найдите первое 0 который предшествует 1 (обратите внимание на случай, когда 0 в конце слова и 1 в начале следующего); изменить 01 в 10выясни сколько 1s вы должны двигаться, и переместить их до конца.