Is there a Phobos function to turn this:

string[] words = "foo bar doo".split();

into:

string[] res = ["foo bar doo",
                "foo doo bar",
                "bar foo doo",
                "bar doo foo",
                "doo foo bar",
                "doo bar foo"];

So basically all combinations of some number of strings into a string array. I suppose there's some generic way to do this too.

On 06/11/2012 10:41 AM, Andrej Mitrovic wrote:
> Is there a Phobos function to turn this:
>
> string[] words = "foo bar doo".split();
>
> into:
>
> string[] res = ["foo bar doo",
>                  "foo doo bar",
>                  "bar foo doo",
>                  "bar doo foo",
>                  "doo foo bar",
>                  "doo bar foo"];
>
> So basically all combinations of some number of strings into a string
> array. I suppose there's some generic way to do this too.

I think "permutation" is a more accurate word in this case. This has been discussed before:

  http://forum.dlang.org/thread/ivd4ug$1rmh$1@digitalmars.com

Ali

-- 
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html

Andrej Mitrovic:

> string[] words = "foo bar doo".split();
>
> into:
>
> string[] res = ["foo bar doo",
>                 "foo doo bar",
>                 "bar foo doo",
>                 "bar doo foo",
>                 "doo foo bar",
>                 "doo bar foo"];

http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version

Using that the code is:

import std.string, std.stdio, std.array;
void main() {
    auto words = "foo bar doo".split();
    auto res = permutations!false(words).map!(p => p.join(" "))().array();
    writeln(res);
}


The output is your desired one:

["foo bar doo", "foo doo bar", "bar foo doo", "bar doo foo", "doo foo bar", "doo bar foo"]

Bye,
bearophile

On Monday, 11 June 2012 at 19:52:38 UTC, bearophile wrote:
> Using that the code is:
>
> import std.string, std.stdio, std.array;
> void main() {
>     auto words = "foo bar doo".split();
>     auto res = permutations!false(words).map!(p => p.join(" "))().array();
>     writeln(res);
> }

Is doCopy really needed as an argument here?

Couldn't this be inferred from the mutability of T instead?

Nordlöw:

> Is doCopy really needed as an argument here?
>
> Couldn't this be inferred from the mutability of T instead?

doCopy is useful, if it's true all the permutation arrays are distinct and dup-ped, otherwise they are all different. It's true by default, so casual users of that generator will avoid bugs. You can set it to false to speed up your code.


Later I have refined the idea, you can see it here, that allows true @nogc code when needed:

struct CartesianPower(bool doCopy=true, T) {
    T[] items;
    uint repeat;
    T[] row;
    uint i, maxN;

    this(T[] items_, in uint repeat_, T[] buffer) pure nothrow @safe @nogc {
        this.items = items_;
        this.repeat = repeat_;
        row = buffer[0 .. repeat];
        row[] = items[0];
        maxN = items.length ^^ repeat;
    }

    static if (doCopy) {
        @property T[] front() pure nothrow @safe @nogc {
            return row.dup;
        }
    } else {
        @property T[] front() pure nothrow @safe @nogc {
            return row;
        }
    }

    @property bool empty() pure nothrow @safe @nogc {
        return i >= maxN;
    }

    void popFront() pure nothrow @safe @nogc {
        i++;
        if (empty)
            return;
        uint n = i;
        size_t count = repeat - 1;
        while (n) {
            row[count] = items[n % items.length];
            count--;
            n /= items.length;
        }
    }
}

auto cartesianPower(bool doCopy=true, T)(T[] items, in uint repeat)
pure nothrow @safe {
    return CartesianPower!(doCopy, T)(items, repeat, new T[repeat]);
}

auto cartesianPower(bool doCopy=true, T)(T[] items, in uint repeat, T[] buffer)
pure nothrow @safe @nogc {
    if (buffer.length >= repeat) {
        return CartesianPower!(doCopy, T)(items, repeat, buffer);
    } else {
        // Is this correct in presence of chaining?
        static immutable err = new Error("buffer.length < repeat");
        throw err;
    }
}

void main() @nogc {
    import core.stdc.stdio;
    int[3] items = [10, 20, 30];
    int[4] buf;
    foreach (p; cartesianPower!false(items, 4, buf))
        printf("(%d, %d, %d, %d)\n", p[0], p[1], p[2], p[3]);
}


Bye,
bearophile

On Sunday, 11 January 2015 at 18:01:09 UTC, bearophile wrote:
> Nordlöw:
>
>> Is doCopy really needed as an argument here?
>>
>> Couldn't this be inferred from the mutability of T instead?
>
> doCopy is useful, if it's true all the permutation arrays are distinct and dup-ped, otherwise they are all different. It's true by default, so casual users of that generator will avoid bugs. You can set it to false to speed up your code.
>
>
> Later I have refined the idea, you can see it here, that allows true @nogc code when needed:
>
> struct CartesianPower(bool doCopy=true, T) {
>     T[] items;
>     uint repeat;
>     T[] row;
>     uint i, maxN;
>
>     this(T[] items_, in uint repeat_, T[] buffer) pure nothrow @safe @nogc {
>         this.items = items_;
>         this.repeat = repeat_;
>         row = buffer[0 .. repeat];
>         row[] = items[0];
>         maxN = items.length ^^ repeat;
>     }
>
>     static if (doCopy) {
>         @property T[] front() pure nothrow @safe @nogc {
>             return row.dup;
>         }
>     } else {
>         @property T[] front() pure nothrow @safe @nogc {
>             return row;
>         }
>     }
>
>     @property bool empty() pure nothrow @safe @nogc {
>         return i >= maxN;
>     }
>
>     void popFront() pure nothrow @safe @nogc {
>         i++;
>         if (empty)
>             return;
>         uint n = i;
>         size_t count = repeat - 1;
>         while (n) {
>             row[count] = items[n % items.length];
>             count--;
>             n /= items.length;
>         }
>     }
> }
>
> auto cartesianPower(bool doCopy=true, T)(T[] items, in uint repeat)
> pure nothrow @safe {
>     return CartesianPower!(doCopy, T)(items, repeat, new T[repeat]);
> }
>
> auto cartesianPower(bool doCopy=true, T)(T[] items, in uint repeat, T[] buffer)
> pure nothrow @safe @nogc {
>     if (buffer.length >= repeat) {
>         return CartesianPower!(doCopy, T)(items, repeat, buffer);
>     } else {
>         // Is this correct in presence of chaining?
>         static immutable err = new Error("buffer.length < repeat");
>         throw err;
>     }
> }
>
> void main() @nogc {
>     import core.stdc.stdio;
>     int[3] items = [10, 20, 30];
>     int[4] buf;
>     foreach (p; cartesianPower!false(items, 4, buf))
>         printf("(%d, %d, %d, %d)\n", p[0], p[1], p[2], p[3]);
> }
>
>
> Bye,
> bearophile

Nice! PR anyone?

On Sunday, 11 January 2015 at 18:01:09 UTC, bearophile wrote:
>> Is doCopy really needed as an argument here?
>>
>> Couldn't this be inferred from the mutability of T instead?
>
> doCopy is useful, if it's true all the permutation arrays are distinct and dup-ped, otherwise they are all different. It's true by default, so casual users of that generator will avoid bugs. You can set it to false to speed up your code.

Couldn't we do a first pass and check that if elements of T are distinct and if so set doCopy to false otherwise true?

Nordlöw:

> Couldn't we do a first pass and check that if elements of T are distinct and if so set doCopy to false otherwise true?

The algorithm you have seen in Rosettacode doesn't care if and what items of the input sequence are duplicated, it handles them as they are all distinct. And them being distinct (or not distinct) doesn't change the desire to use something like doCopy to have dup-ped output arrays, so I don't understand what you are trying to say.

The purpose of doCopy is similar of the difference between File.byLine and File.byLineCopy (originally I suggested to give a doCopy argiment to byLine too, for safety. Andrei said no. Later experience has shown I was right and we have added byLineCopy, but now the default line iteration is the non-copying one, that is less safe).

Bye,
bearophile