Ordered conjunction of two arrays.
I have the following situation. There are two arrays, each containing a subset of a total set of items having a natural order.
For example, let us say that we are representing cardinal numbers as Strings. The complete set might be:
{"first","second","third","fourth","fifth"}
Important: the complete set and natural order are UNKNOWN to the program and cannot be determined in any way.
Our two arrays might be:
{"third","fifth"}
{"first","third"}
Also important: although the complete set and natural order are unknown, the contents of the arrays are assumed to be in the correct order.
What the code has to do is create a conjunction of the two arrays, ordered as a "best guess" using the hints provided by the arrays. In the above case, both arrays contain "third" - and each contains only one element either before or after - hence, the total order is known to be:
{"first","third","fifth"}
This type of case should be the majority case by far. However, cases like this are also possible:
{"second","third"}
{"first","third","fourth"}
This is where our "best guess" comes in. Both arrays contain "third", and one array contains "fourth" after it - hence, the last two elements must be "third" and then "fourth". However, each array contains one distinct element prior to "third" - "second" in the first array and "first" in the second array. In this case there is no way to know which comes first, so we can just pick one at random (or assume that one of the arrays has priority).
The conjoined array is a "best guess" because all but one part of it is known to be correct, but that one part might be wrong.
I have this situation right now in real life and I am wondering whether there is some way to avoid writing really clever routines to do all this. Specifically:
a) Is there a utility method somewhere that I have missed which could help?
b) Is there a bit of code somebody knows about that can do this?
c) Is there a mathematical or other tricky short-cut solution?
Thanks for any comments.
Drake
[2880 byte] By [
Drake_Duna] at [2007-10-2 6:26:41]
> a) Is there a utility method somewhere that I have> missed which could help?NoBtw. Are the instances in the arrays always strings? (I'm asking because you must at least make sure that the instances has overridden the equals method)Kaj
kajbja at 2007-7-16 13:28:31 >
As it happens, yes, they are always Strings, but I have total control over the implementation. I could always wrap in a mutable (non-final) class or something.Drake
public static String[] merge(final String[] a, final String[] b) {
ArrayList<String> c = new ArrayList<String>();
for (int numA = 0, numB = -1; numA < a.length; numA++) {
for (int i = b.length - 1; i > numB; i--) {
if (b[i].equals(a[numA])) {
for (int n = numB + 1; n <= i; n++) {
c.add(b[n]);
}
numB = i;
}
}
c.add(a[numA]);
}
String[] result = new String[c.size()];
c.toArray(result);
return result;
}
Would do what you're asking, giving preference to the first array when there's no way to determine what order a set of elements should have. If a was 1,3,4,5,6 and b was 1,2,6 it would come out 1,1,3,4,5,2,6,6. All we know is that 3, 4, 5 and 2 are between 1 and 6, so it will give preference to the first three elements and produce them in order before appending the element(s) from the second array into it.
If you don't want duplicate values it would require modification.
Dang. Can I be as cool as you when I grow up?
That is pretty much what I was looking for. Actually I have realized that my requirements are slightly different from what I originally stated, but the methodology is what I needed.
I will post the new requirements and the completed code to this thread when I have finished. Thanks!
Drake
Okay, I have a working solution, so thanks for the help, Kablair. In case you are interested, here is the actual situation.
I need to combine two ordered arrays of Strings, like I said before. However, there are two addition points:
1) The combined array should not contain duplicates
2) The order within either array is right in MOST cases - but it is not impossible for it to be wrong.
Below is the code I devised to do the job. I guess the approach I am using is not 100% obvious from the code and comments but I am too drunk and lazy to actually explain the algorythm when at most one person will be interested and even that is dubious.
Anyway, thanks again for the help.
private String[] combineReadings(String[] existingReadings, String[] freshReadings) {
ArrayList<String> builtReadingList = new ArrayList<String>();
// build an ArrayList of the new readings so that we can strip the list down as we go
ArrayList<String> freshReadingList = new ArrayList<String>(freshReadings.length);
for (String element: freshReadings) freshReadingList.add(element);
int prependedElements;
boolean alreadyExists;
String subjectFreshReading;
for (String subjectExistingReading: existingReadings) { // for each existing reading
// determine how many (if any) elements precede the same reading in the fresh list
prependedElements = -1;
for (int x = 0; x < freshReadingList.size(); x++)
if (subjectExistingReading.equals(freshReadingList.get(x))) {
prependedElements = x;
break;
}
// add the item in question along with any legitimately prepended elements in the fresh list
if (prependedElements == -1) // there was no match in the list of new ones
builtReadingList.add(subjectExistingReading); // so just add the one reading from the existing list
else { // deal with the match and its forerunners
for (int x = 0; x < prependedElements; x++) { // deal with the prepended elements
alreadyExists = false;
subjectFreshReading = freshReadingList.remove(0);
for (int y = 0; y < existingReadings.length; y++) // check against each of the existing readings
if (existingReadings[y].equals(subjectFreshReading)) {
alreadyExists = true;
break;
}
if (!alreadyExists) // if it does not exist in the existing list, add it - otherwise chuck it
builtReadingList.add(subjectFreshReading);
}
builtReadingList.add(freshReadingList.remove(0)); // move the matched reading itself
}
}
builtReadingList.addAll(freshReadingList); // move anything left over in the fresh list
String[] builtReadings = new String[builtReadingList.size()];
return builtReadingList.toArray(builtReadings);
}
Drake
> Dang. Can I be as cool as you when I grow up?
Er, is that sarcasm?
> Okay, I have a working solution, so thanks for the
> help, Kablair. In case you are interested, here is
> the actual situation.
>
> I need to combine two ordered arrays of Strings, like
> I said before. However, there are two addition
> points:
>
> 1) The combined array should not contain duplicates
> 2) The order within either array is right in MOST
> cases - but it is not impossible for it to be wrong.
>
> Below is the code I devised to do the job. I guess
> the approach I am using is not 100% obvious from the
> code and comments but I am too drunk and lazy to
> actually explain the algorythm when at most one
> person will be interested and even that is dubious.
I think all you needed was to add a !c.contains(element) check before adding it.
public static String[] merge(final String[] a, final String[] b) {
ArrayList<String> c = new ArrayList<String>();
for (int numA = 0, numB = -1; numA < a.length; numA++) {
for (int i = b.length - 1; i > numB; i--) {
if (b[i].equals(a[numA])) {
for (int n = numB + 1; n <= i; n++) {
if (!c.contains(b[n]))
c.add(b[n]);
}
numB = i;
}
}
if (!c.contains(a[numA]))
c.add(a[numA]);
}
String[] result = new String[c.size()];
c.toArray(result);
return result;
}
Does that not solve your problem? Seems a bit simpler.
> > Dang. Can I be as cool as you when I grow up?
>
> Er, is that sarcasm?
Well, there was a little humor in it, but I was genuinely impressed.
> Does that not solve your problem? Seems a bit
> simpler.
Two things:
First, I totally missed that I could use contains() because I forgot that it tests using equals() and not ==... hence because Strings override equals() to test for the same characters two different Strings with the same content are the same in the eyes of contains(). Thanks for pointing that out. Also I have realized that I can cut down on the lines of code even more by just using a HashSet instead of an ArrayList.
Second, I failed (again) to expess the conditions clearly enough. In the case that the ordering of the first and second arrays conflict, as in the case that both contain elements prepending a common element and there is no way to tell which is first (the {2,3} {1,3} scenario), preferrence should be given to the first array. Your code will give preferrence to the second array.
What I have now works, but for the sake of learning I will rethink it and try to do it in a neat little loop nest like in your code.. give some time as I am busy studying for the Japanese Proficiency Test level 1, which I take on Sunday!
Drake
Use a LinkedHashSet instead of a HashSet because you need to guarantee order not just that there's no duplicates.Changing which array gets priority is also just a matter of aliasing to different variables, not changing the algorithm. EIther way, as long as it works and is fast enough do whatever works! Just be careful about the HashSet thing, it might appear to work and then stop working sometime in the future because of the order.
