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
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
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
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
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