Ben
BAN USERDoes the solution need to be made generic? If so, how are the lengths of input strings bound?
If the pre-sorted string is always small in distinct letters relative to the string being sorted, insert is acceptable as other sorting algorithms suffer when most of the string is already 'sorted'.
Insert sort is also preferable for small strings in general. That is why it is one way to better performance of quicksort after a threshold of sub-string/array has been reached.
Observing letters not included in the sorting string do not change position related to one another, one solution is to use a new Character data object implementing comparable interface where f = 0, g = 1, h = 2, a = 3, b = 4, else = 99. Then use merge sort which is a 'stable' sort, preserving positions of 'equal' items relative to one another.
What are your thoughts on this? Worked on paper for me with a couple small examples. Taking for granted that words with same spelling are equivalent.
1. build a sorted map to hold the count for each character
2. for each character in the original sequence,
2.a. sum of characters coming before that one in the map (including duplicates)
2.b. while looping for ^, also count number of duplicate characters
2.c.1. calculate (length - position)! * value from 2.a
2.c.2. IF result from 2.b !=0, divide 2.c.1 value by (duplicates*2)
2.d subtract one from the map value corresponding to that character in the original sequence
2.e add calculated value to running total
Good idea to ask questions. Here are some more.
- Ben October 29, 2012Does the graph datatype contain information that could be discarded?
Is it necessary to code for minimum size of serialized representation?
One solution is to use industry standard like @XmlRootElement on the graph data type. You can set to ignore variables for json or xml serialization with appropriate annotations as well.
If the tree is binary, you could serialize the objects in an array to get rid of some of the bloat.