Word break problem: Difference between revisions

=={{header|Picat}}==

===Non-determinism using member/2===

<code>s/2</code> checks all possible combinations. It uses <code>member/2</code> to select some element from Dict and backtracks if no solution is found.

<lang Picat>main =>

Tests = [["aab", ["a", "aa", "b", "ab", "aab"]],

["abba", ["a", "aa", "b", "ab", "aab"]],

["aa b", ["a", "aa", "b", "ab", "aab"]],

["abcd", ["abc", "a", "ac", "b", "c", "cb", "d"]],

["abbc", ["abc", "a", "ac", "b", "c", "cb", "d"]],

["abcbcd", ["abc", "a", "ac", "b", "c", "cb", "d"]],

["acdbc", ["abc", "a", "ac", "b", "c", "cb", "d"]],

["abcdd", ["abc", "a", "ac", "b", "c", "cb", "d"]]

],

foreach([String,Dict] in Tests)

println([string=String,dict=Dict]),

All = findall(S, S = s3(Dict,String)),

println(All),

nl

end,

nl.

s(Dict,String) = S =>

S = [],

while(S.flatten != String, S.flatten.len < String.len)

member(D,Dict), % pick some element in Dict

S := S ++ [D]

end,

S.flatten==String.</lang>

{{out}}

<pre>[string = aab,dict = [a,aa,b,ab,aab]]

[[a,a,b],[a,ab],[aa,b],[aab]]

[string = abba,dict = [a,aa,b,ab,aab]]

[[a,b,b,a],[ab,b,a]]

[string = aa b,dict = [a,aa,b,ab,aab]]

[]

[string = abcd,dict = [abc,a,ac,b,c,cb,d]]

[[abc,d],[a,b,c,d]]

[string = abbc,dict = [abc,a,ac,b,c,cb,d]]

[[a,b,b,c]]

[string = abcbcd,dict = [abc,a,ac,b,c,cb,d]]

[[abc,b,c,d],[a,b,c,b,c,d],[a,b,cb,c,d]]

[string = acdbc,dict = [abc,a,ac,b,c,cb,d]]

[[a,c,d,b,c],[ac,d,b,c]]

[string = abcdd,dict = [abc,a,ac,b,c,cb,d]]

[[abc,d,d],[a,b,c,d,d]]</pre>

===Non-determinism using member/2 and append/3===

<code>s2/2</code> is more efficient. It uses <code>append/3</code> to extract the found prefix from the string.

<lang Picat>s2(Dict,String) = S =>

String2 = copy_term(String),

S = [],

while(S.flatten != String, S.flatten.len < String.len)

% Pick an element from Dict

member(D,Dict),

% Check that it fits and remove it from the string.

% If not: backtrack

append(D,String3,String2),

% ok!

String2 := String3,

S := S ++ [D]

end,

S.flatten==String.</lang>

===Using recursion===

<code>s3/2</code> use the same idea as <code>s2/2</code> but use recursion. Neater and more efficient.

<lang Picat>s3(Dict,String) = S =>

s3(Dict,String,S).

s3(_Dict,[],[]).

s3(Dict,String,[E|S]) :-

member(E,Dict),

append(E,String2,String),

s3(Dict,String2,S).</lang>

===Some tests===

Here is the test engine.

<lang Picat>main =>

garbage_collect(300_000_000),

_ = random2(),

Chars = "ab",

Dict = ["a", "aa", "b", "ab", "aab"],

println(dict=Dict),

String = [Chars[random(1,Chars.len)] : _ in 1..11],

% The tested strings

% String := "abbaabba",

% String := "babbbbaabbababb",

% String := "babbbbaabbababbaaaaababbaaabbb",

% String := "babbbbaabbababbaaaaababbaaabbbbaaabbbaba",

% String := "aabababbbaaabaababaaabababaaabbabbaabbba",

println(string=String),

All = findall(S, S = s3(Dict,String)),

Len = All.len,

if Len < 100 then

println(All)

end,

println(len=All.len),

nl.</lang>

As can be seen by this summary, <code>s3/2</code> is the most efficient of these versions. <code>s/2</code> is too slow but for the simplest examples.

{{out}}

<pre>dict = [a,aa,b,ab,aab]

string = abbaabba

[[a,b,b,a,a,b,b,a],[a,b,b,a,ab,b,a],[a,b,b,aa,b,b,a],[a,b,b,aab,b,a],[ab,b,a,a,b,b,a],[ab,b,a,ab,b,a],[ab,b,aa,b,b,a],[ab,b,aab,b,a]]

len = 8

s: 0.012s

s2: 0.0s

s3: 0.0

Dict = ["a", "aa", "b", "ab", "aab"],

string = babbbbaabbababb

[[b,a,b,b,b,b,a,a,b,b,a,b,a,b,b],[b,a,b,b,b,b,a,a,b,b,a,b,ab,b],[b,a,b,b,b,b,a,a,b,b,ab,a,b,b],[b,a,b,b,b,b,a,a,b,b,ab,ab,b],[b,a,b,b,b,b,a,ab,b,a,b,a,b,b],[b,a,b,b,b,b,a,ab,b,a,b,ab,b],[b,a,b,b,b,b,a,ab,b,ab,a,b,b],[b,a,b,b,b,b,a,ab,b,ab,ab,b],[b,a,b,b,b,b,aa,b,b,a,b,a,b,b],[b,a,b,b,b,b,aa,b,b,a,b,ab,b],[b,a,b,b,b,b,aa,b,b,ab,a,b,b],[b,a,b,b,b,b,aa,b,b,ab,ab,b],[b,a,b,b,b,b,aab,b,a,b,a,b,b],[b,a,b,b,b,b,aab,b,a,b,ab,b],[b,a,b,b,b,b,aab,b,ab,a,b,b],[b,a,b,b,b,b,aab,b,ab,ab,b],[b,ab,b,b,b,a,a,b,b,a,b,a,b,b],[b,ab,b,b,b,a,a,b,b,a,b,ab,b],[b,ab,b,b,b,a,a,b,b,ab,a,b,b],[b,ab,b,b,b,a,a,b,b,ab,ab,b],[b,ab,b,b,b,a,ab,b,a,b,a,b,b],[b,ab,b,b,b,a,ab,b,a,b,ab,b],[b,ab,b,b,b,a,ab,b,ab,a,b,b],[b,ab,b,b,b,a,ab,b,ab,ab,b],[b,ab,b,b,b,aa,b,b,a,b,a,b,b],[b,ab,b,b,b,aa,b,b,a,b,ab,b],[b,ab,b,b,b,aa,b,b,ab,a,b,b],[b,ab,b,b,b,aa,b,b,ab,ab,b],[b,ab,b,b,b,aab,b,a,b,a,b,b],[b,ab,b,b,b,aab,b,a,b,ab,b],[b,ab,b,b,b,aab,b,ab,a,b,b],[b,ab,b,b,b,aab,b,ab,ab,b]]

len = 32

s: 22.513s

s2: 0s

s3: 0s

Dict = ["a", "aa", "b", "ab", "aab"],

string = babbbbaabbababbaaaaababbaaabbb

len = 6144

s2: 0.088s

s3: 0.012s

Dict = [a,aa,b,ab,aab]

string = babbbbaabbababbaaaaababbaaabbbbaaabbbaba

len = 73728

s2: 1.466s

s3: 0.341

sdict = [a,aa,b,ab,aab]

string = aabababbbaaabaababaaabababaaabbabbaabbba

len = 884736

s2: 19.431 seconds

s3: 3.81 seconds</pre>