D implementation of ZS1 algorithm to enumerate integer partitions. See: http://en.wikipedia.org/wiki/Partition_(number_theory) (in English http://ja.wikipedia.org/wiki/自然数の分割 (日本語)

integer_partition.d

import std.traits;

/**
 * Returns: InputRange which returns integer partitions of $(D_PARAM n) in lexicographic order.
 * See_Also: ZS1 in "Fast Algorithms for Generating Integer Partitions"
 */
@safe pure nothrow
auto integerPartitions(UInt)(UInt n)
if (isIntegral!UInt && isUnsigned!UInt)
{
    struct IntegerPartitions
    {
        static assert(isInputRange!(typeof(this)));
        static assert(is(ElementType!(typeof(this)) == immutable(UInt)[]));

        this(UInt n) pure nothrow
        {
            x = new UInt[n];
            x[0] = n;
            x[1..$] = 1;
            m = h = 0;
        }

        @property auto front() const pure
        {
            return x[0..m+1].idup;
        }

        auto popFront() pure nothrow
        {
            if(x[0] == 1)
            {
                empty_ = true;
                return;
            }

            if (x[h] == 2)
            {
                m++;
                x[h] = 1;
                h--;
            }
            else
            {
                auto r = x[h]-1;
                auto t = m-h+1;
                x[h] = r;
                while(t >= r)
                {
                    h++;
                    x[h] = r;
                    t -= r;
                }
                if (t == 0)
                {
                    m = h;
                }
                else
                {
                    m = h+1;
                }
                if (t > 1)
                {
                    h++;
                    x[h] = t;
                }
            }
        }

        @property auto empty() const pure nothrow
        {
            return empty_;
        }
    private:
        UInt[] x;
        UInt m, h;
        bool empty_;
    }
    return IntegerPartitions(n);
}

unittest
{
    import std.algorithm;

    //Example shown in Wikipedia
    assert(equal(integerPartitions(4u),
                 [[4], [3,1], [2,2],
                  [2,1,1], [1,1,1,1]]));

    // Example shown in the paper
    assert(equal(integerPartitions(5u),
                 [[5], [4,1], [3,2],
                  [3,1,1], [2,2,1], [2,1,1,1],
                  [1,1,1,1,1]]));
}