Steve Wampler wrote:
> The new version is attached. (It could be sped up more by adding a
> prepass through the states to precompute gn(state). This version
> computes gn(state) only if it hasn't been computed already, which
> costs two extra table lookups in the (n^2)/2 part of the algorithm.
> It feels cleaner to me, however.)
I thought I'd put out one more variant (then I'll stop, I promise!).
It occurred to me this morning that, while the previous version(s)
I posted produce the output on completed equivalence classes by
removing each pair from the class in turn and coupling it with
all of the remaining pairs (discarding invalid couples) in the
class, it's also possible to perform the coupling of pairs just
*before* adding a new pair into the class. The result is a
single pass instead of two, so this version is slightly faster.
I actually prefer the previous solution because it more cleanly
separates the construction of the equivalence classes from their
processing, so you can more easily adapt it to doing something
else with the classes (such as output the class with the most
pairs, or whatever). [Not that it's hard to adapt this new
approach, either - but...]
Anywhere, here's the latest solution. I probably have to leave
this alone now (and do some real work), but if someone does
implement Raja's alternative algorithm for building signatures
numerically, I'd like to see it! [Or if you find other approaches,
such as Barry's approach of grouping equivalence class elements
using sort().] I've really enjoyed seeing all of the solutions
so far, and the discussions.
--
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.
link factors
procedure main()
local min, max
st := &time
equivClasses := table()
statePairs := table()
every put(states := [], map(!getStates())) # Make case insignificant
min := proc("min",0)
max := proc("max",0)
# Build a table of equivalence classes (all state pairs in the
# same equivalence class have the same characters in them)
# Output new pair couples before adding each state pair.
every (state1 := |get(states)) & (state2 := !states) do {
if state1 ~== state2 then {
statePair := min(state1, state2)||":"||max(state1,state2)
signature := getClassSignature(state1, state2)
/equivClasses[signature] := set()
if /statePairs[statePair] := set(state1, state2) then {
every *(statePairs[statePair] **
statePairs[pair := !equivClasses[signature]]) == 0 do {
write(statePair, " and ", pair)
}
insert(equivClasses[signature], statePair)
}
}
}
write(&errout, "Time: ", (&time-st)/1000.0)
end
# Build a signature identifying the equivalence class for state pair s.
# (Godelization).
procedure getClassSignature(s1, s2)
static G
initial G := table()
/G[s1] := gn(s1)
/G[s2] := gn(s2)
return G[s1]*G[s2]
end
# Compute the Godel number for a string (letters only)
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
procedure getStates()
return ["Alabama", "Alaska", "Arizona", "Arkansas", "California",
"Colorado", "Connecticut", "Delaware", "Florida", "Georgia",
"Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas",
"Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts",
"Michigan", "Minnesota", "Mississippi", "Missouri", "Montana",
"Nebraska", "Nevada", "New Hampshire", "New Jersey",
"New Mexico", "New York", "North Carolina", "North Dakota",
"Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island",
"South Carolina", "South Dakota", "Tennessee", "Texas", "Utah",
"Vermont", "Virginia", "Washington", "West Virginia",
# "NeW kORy", "nEW KorY", "Wen Kory", "York New", "Kory New",
# "York New", "York New", "New Kory", "Wen Kory", "Kory New",
"Wisconsin", "Wyoming"]
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
