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

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

Ввод: 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;
}

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


algorithm data-structures subset gray-code
person Mark Lin    schedule 21.12.2015    source источник
comment
Я не понимаю? // if yes, set the corresponding jth bit of x as 1.? у вас уже есть i в качестве установленного представления, зачем вам еще x? Кроме того, какой язык вы используете?   -  person Pham Trung    schedule 21.12.2015
comment
Разве это не просто long i=(1<<n)-1; while (i--) {/*add i to results*/}?   -  person m69 ''snarky and unwelcoming''    schedule 22.12.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

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

  • внешний цикл: создайте версию, в которой используется 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.
}

by: 

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

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

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

person MrSmith42    schedule 21.12.2015