使用不同的二进制数查找给定集合的子集

Question

所以挑战在于设计一种算法来打印给定集合的子集 n。

让我们设置 n 相等：

 n = {a,b,c}

在这个 stack overflow article 上有一个来自@Piva 的答案，它使用 "Each number from 0 to 2^n gives a unique subset in its binary representation"

的事实解决了这个问题

我写了一个Javascript版本的@Piva的代码，效果很好。除了一行之外，我了解大部分内容：

if(((i>>j) & 1) === 1)

我想我明白这行代码将 i 位右移，将 j 个零添加到 i 的二进制表示形式的开头。我也理解位明智 & 正在比较 i >>j 和 1 并查看输出 i >> 的第一位是否打开。

但我不明白这个操作如何识别唯一的二进制表示以及为什么 if(((i>>j) & 1) === 1) 为真意味着我们有一个给定的 n.

的唯一子集

这是我的 Javascript 版本：

    function SubsetBuilder(set) {
        this.set = set;

    }

    SubsetBuilder.prototype.getSubsets = function () {
        var self = this;

        if (!self.set)
            return null;

        //recursive way, do next
        var getSubsetsAll = function (originalSet) {
            if (!originalSet) {
                return;
            }
        }

        var n = this.set.length;
        for(var i = 0; i < (1<<n); i++) {
            var subset = [];
            for (var j = 0; j < n; j++) {
                console.log('i:' + i + ", binary: " + i.toString(2));
                console.log('j:' + j + ", binary: " + j.toString(2));
                console.log('(i >> j):');
                console.log((i >> j));
                console.log('((i>>j) & 1):');
                console.log(((i >> j) & 1));
                if(((i>>j) & 1) === 1){ // bit j is on
                    subset.push(this.set[j]);
                }
                console.log('-------------------');
            }
            console.log(subset);
            console.log('-------------------');
        }
    }

    var set = ['a', 'b', 'c'];
    var obj = new SubsetBuilder(set);
    obj.getSubsets();

Answer 1

if(((i>>j) & 1) === 1) 检查 i 的第 j 位是否已设置。

要了解其工作原理，请考虑二进制 101b 中的数字 5。 >> 只是一个移位（或者等价地，除以 2ⁿ）并且 & 1 掩盖了除最低有效位以外的所有位。

(101b >> 0) & 1 = (101b & 1) = 1
(101b >> 1) & 1 = ( 10b & 1) = 0
(101b >> 2) & 1 = (  1b & 1) = 1

所以一旦我们了解了位提取的工作原理，我们就需要了解为什么位提取等同于子集包含：

以下是我们如何将二进制数 0-7 映射到 {A,B,C} 的子集

0: 0 0 0   => {     }
1: 0 0 1   => {    A}
2: 0 1 0   => {  B  }
3: 0 1 1   => {  B A}
4: 1 0 0   => {C    }
5: 1 0 1   => {C   A}
6: 1 1 0   => {C B  }
7: 1 1 1   => {C B A}

显然我们已经列出了所有子集。

希望您现在可以明白为什么对 i 的第 j 位的测试等同于将第 j 个对象包含到第 i 个子集中。

使用不同的二进制数查找给定集合的子集

Using distinct binary numbers to find subsets of a given set

javascript

c#

java

algorithm

big-o