www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Build all combinations of strings

reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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.
Jun 11 2012
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Jun 11 2012
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jun 11 2012
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Jan 11 2015
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jan 11 2015
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Jan 11 2015
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Jan 11 2015
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Jan 11 2015