Anagram generator: Difference between revisions
Content deleted Content added
Line 136:
piety pizza tram
pizza pyrite tam</syntaxhighlight>
=={{header|jq}}==
This entry provides a number of anagram-related functions, all based
on the profiling of words by the frequency counts of their constituent
letters. The emphasis is on a reasonable level efficiency within the context of general-purpose utility
functions.
In general, a streaming approach is taken, in part for speed and to minimize
memory requirements, and in part to highlight jq's support
for streaming.
Phrasal anagrams are not limited by a predetermined length,
and are computed as a stream consisting of a sorted list
of words, e.g. for "firefox", one phrasal anagram would be presented as:
<pre>
["off","re","xi"]
</pre>
In order to motivate the helper functions, consider first the task
of generating anagrams of a word, $word. In this case,
we have only to construct a listing of relevant words,
which can be done by calling our "dictionary" construction
function:
<pre>
dict(inputs; $word; $word|length)
</pre>
Here, the last argument ensures that only words having the same length
as the target word are selected.
Next, consider the task of generating anagrammatic phrases wherein
each word has a minimum length of 2. This would be accomplished by:
<pre>
dict(inputs; $word; 2)
| anagram_phrases($letters)
</pre>
'''Use of gojq'''
The program presented here has been tested using both jq, the C-based implementation,
and gojq, the Go implementation of jq, but in the latter case
with the additional definition:
<pre>
def keys_unsorted: keys;
</pre>
'''Generic Functions'''
<syntaxhighlight lang=jq>
def count(stream): reduce stream as $x (0; .+1);
# remove adjacent duplicates
def once(stream):
foreach stream as $x ({prev: null};
if $x == .prev then .emit = null else .emit = $x | .prev = $x end;
select(.emit).emit);
# one-for-one subtraction
# if . and $y are arrays, then emit the array difference, respecting multiplicity;
# similarly if both are strings, emit a string representing the difference.
def minus($y):
if type == "array"
then reduce $y[] as $x (.;
index($x) as $ix
| if $ix then .[:$ix] + .[$ix+1:] else . end)
else explode | minus($y|explode) | implode
end;
# bag of words
def bow(stream):
reduce stream as $word ({}; .[($word|tostring)] += 1);
</syntaxhighlight>
'''Anagrams'''
<syntaxhighlight lang=jq>
# Input: a string
def profile: bow( explode[] | [.] | implode);
# Comparison of profiles
# . and $p2 should be profiles
def le($p2):
. as $p1
| all( keys_unsorted[]; $p1[.] <= $p2[.]);
def eq($p2):
. as $p1
| all( keys_unsorted + ($p2|keys_unsorted) | unique[]; $p1[.] == $p2[.]);
# Construct a list of relevant words using the given stream.
# $min is the a-priori minimum word length and
# so if $min is the length of $word, we are looking for exact anagrams:
def dict(stream; $word; $min):
($word|length) as $length
| ($word|profile) as $profile
| if $length == $min
then [stream | select(profile|eq($profile))]
else [stream
| select(length >= $min and
length <= $length and
(profile|le($profile)))]
end ;
# Input: an array of admissible words.
# Output: a stream of anagrams of $word
def anagram($word):
($word|profile) as $profile
| .[]
| select(profile|eq($profile));
# Input: an array of admissible words.
# Output: a stream of subanagrams of $word
# regarding each occurrence of a letter as distinct from all others
def subanagrams($word):
($word|profile) as $profile
| .[]
| select(profile|le($profile));
# input: an array to be extended with an additional dictionary word.
# output: a stream of arrays with additional words selected from the characters in the string $letters.
# The input array should be in alphabetical order; if so, so will the output array.
def extend($letters; $dict):
if $letters == "" then .
else . as $in
| ($dict|subanagrams($letters)) as $w
| select(if ($in|length) > 0 then $in[-1] <= $w else true end)
| ($letters | minus($w)) as $remaining
| ($in + [$w]) | extend($remaining; $dict)
end;
def anagram_phrases($letters):
. as $dict
| once([] | extend($letters; $dict));
# Global: $anagram $word $min
def main:
if $anagram
then dict(inputs; $word; $word|length)[]
else dict(inputs; $word; $min)
| anagram_phrases($word)
end ;
main
</syntaxhighlight>
'''Invocation template'''
<pre>
< unixdict.txt jq -ncrR --arg word WORD --argjson anagram BOOLEAN --argjson min MIN -f anagram-generator.jq
</pre>
where:
* WORD is a string (normally, a word)
* BOOLEAN determines whether anagrams or anagrammatic phrases are sought
* MIN is the minimum length of admissible words to be used if $anagram is false
'''Examples'''
Anagram
<pre>
# Invocation:
< unixdict.txt jq -nrR --arg word read --argjson anagram true --argjson min 3 -f anagram-generator.jq
dare
dear
erda
read
</pre>
Anagrammatic phrases
<pre>
# Invocation:
< unixdict.txt jq -ncR --arg word firefox --argjson min 2 -f anagram-generator.jq
"firefox" / 2
["ex","fir","of"]
["ex","for","if"]
["ex","fro","if"]
["ex","ir","off"]
["ex","off","ri"]
["fe","fir","ox"]
["fe","fix","or"]
["fe","for","ix"]
["fe","for","xi"]
["fe","fox","ir"]
["fe","fox","ri"]
["fe","fro","ix"]
["fe","fro","xi"]
["fifo","rex"]
["fire","fox"]
["fix","fore"]
["fix","of","re"]
["fox","if","re"]
["if","of","rex"]
["ix","off","re"]
["ix","offer"]
["off","re","xi"]
["offer","xi"]
</pre>
=={{header|Julia}}==
|