Каков наиболее эффективный способ создания подмножеств?

Question

Я хочу сделать следующее:

Ввод: n, например n = 3

Вывод: {000, 001, 010, 011, 100, 101, 110, 111}, сгенерировать все подмножества, и мне все равно порядок подмножеств

Я реализовал алгоритм:

for (long i = 0, max = 1 << n; i < max; i++) {
    for (int j = 0; j < n; j++) {
        // check if the j bit is set to 1
        int isSet = (int) i &  1 << j;
        if (isSet > 0) {
            // if yes, set the corresponding jth bit of x as 1.
        }
    }
    // add x to results;
}

Я знаю, что Серый Кодекс может сделать что-то подобное. Но мне интересно, какой из них является наиболее эффективным способом создания подмножеств?

Answer 1

Я не уверен, что именно вы подразумеваете под "наиболее эффективным", но если вы ищете оптимизацию скорости, вы можете только надеяться на некоторые незначительные оптимизации, потому что я сомневаюсь, что вы сможете найти более быстрый алгоритм.

Если вы хотите повысить скорость, попробуйте (всегда пишите, если это действительно ускоряет ваш код!):

• внешний цикл: сделать версию, которая использует int вместо long если max достаточно мал, чтобы поместиться в int, Это может быть быстрее.
• внутренний цикл: вы можете вычислить все маски битовых тестов вне обоих циклов и сохранить их в массиве. Таким образом, вы замените 1 << j поиском массива. [Я не уверен, что это улучшит скорость, но стоит попробовать]

Вы также должны заменить

int isSet = (int) i &  1 << j;
if (isSet > 0) {
    // if yes, set the corresponding jth bit of x as 1.
}

от:

if (0!=(int) i &  1 << j) {
    // if yes, set the corresponding jth bit of x as 1.
}

кроме случаев, когда вам нужна переменная isSet снова где-то еще.

Относительно кода Грея: это минимизирует количество битовых изменений, но я не понимаю, как это могло бы улучшить генерацию всех подмножеств, но код Грея полезен, если вы заинтересованы в порядке подмножеств, которые имеют характеристику, что они отличаются только в одном элементе, проходя через них.