powerset.d

import std.algorithm, std.exception, std.random, std.range, std.stdio;

PowerSet!R powerSet(R)(R range) if(isRandomAccessRange!R)
{
    return typeof(return)(range);
}

auto powerSet(R)(R range) if(!isRandomAccessRange!R && !isInfinite!R)
{
    return powerSet(array(range));
}

struct PowerSet(R) if(isRandomAccessRange!R)
{
    this(R set)
    {
        enforce(set.length < 64, "power sets with more than 63 set members unsupported (2^64).");
        _set = set;
    }

    bool empty() const
    {
        return _count == length;
    }

    auto front()
    {
        return opIndex(0);
    }

    auto opIndex(size_t idx)
    {
        assert(idx < length);
        import core.bitop;

        static struct SubSet
        {
            size_t length()
            {
                size_t res = popcnt(_mask & uint.max);
                static if (size_t.sizeof == 8)
                    res += popcnt(_mask >> 32 & uint.max);
                return res;
            }

            ElementType!R front()
            {
                return _set[bsr(_mask)];
            }

            void popFront()
            {
                _mask &= ~(1UL << bsr(_mask));
            }

            bool empty()
            {
                return _mask == 0;
            }

            R _set;
            size_t _mask;
        }
        return SubSet(_set, _count + idx);
    }

    void popFront()
    {
        ++_count;
    }

    size_t length() const
    {
        return 1UL << _set.length;
    }

    R _set;
    ulong _count;
}

void main() {
    immutable setSize = 22;
    auto set = take(rndGen, setSize);
    auto pset = powerSet(set);
    assert(pset.length == 2UL ^^ setSize);
    foreach(subset; pset) {}
}