I had started programming when I saw that Mukherji posted
a nearly identical solution.
Here, for what it is worth, is my re-implementation of
same. If you strip out the comments, the code is quite
small and heavily Icon-flavored.
Note however that anagrams within the input strings are
noted and rejected.
-- Michael Glass
Valparaiso University
# Program for the pairs-of-states problem on the Unicon
# This program implements Raja Mukherji's algorithm.
#
record pair(u,v)
link factors
link getStates
procedure main()
# The n2s table maps a godel number back to its source string.
# Populate n2s with one entry for every string in the dataset.
#
n2s := table()
every s := !getStates() do
if not (/n2s[gn(s)] := s) then
write("Ignoring ", s, " as an anagram of ", n2s[gn(s)])
# The pairs table is populated by the godel numbers of
# all concatenated string pairs UV, where gn(U) < gn(V)
# pairs[u*v] -> a record containing u and v.
#
pairs := table()
every (u := key(n2s)) < (v := key(n2s)) do {
if (/pairs[u*v] := pair(u, v)) then next
# If u*v = u'*v', then the strings UV and U'V'
# are anagrams.
write(n2s[u], " , ", n2s[v], " <=> ",
n2s[pairs[u*v].u], " , ", n2s[pairs[u*v].v])
}
write(tot)
end
# Anagram-independent Godel number for a string.
# (This is the same as to Raja Mukherji's getValue())
#
# Where sigma_i is the i-th character of the alphabet,
# and p_i is the i-th prime:
#
# gn(s) = prod( (p_i)^(occurrences of sigma_i in s) )
#
# For example: gn("baddaa") = 2^3 * 3^1 * 7^2
#
# The godelization of the concatenation equals the
# product of the godelizations: gn(UV) = gn(U)*gn(v)
#
procedure gn(s)
static xlate
local p, i, z
initial {
xlate := table(1)
p := create prime()
every i := 1 to 26 do
xlate[&lcase[i]] := xlate[&ucase[i]] := @p
}
z := 1
every z *:= xlate[!s]
return z
end
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Unicon-group mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/unicon-group
