Reordering an array based on the change in a value at one index
I have a problem with reordering an array when one of it's values is changed.
I can state the problem as follows :
Suppose there is an array of size three(3), consisting of elements 0, 1 and 2 at the respective indices. Now if the value at any one of the indices is changed, like 0 is changed to 2, then the array should be reordered as 2, 0, 1.
One more change like 0 is changed to 1, should make the array as 2,1,0.
The problem can be summarised as:
a.) When the user changes the value at a particular index, the other values should be reordered in such a way that apart from the changed index the other values maintain the ascending order sequence in which it was originally. For example, if I change value 101 to 10, then all the values starting from 10 should be incremented by one.
b.) There cannot be any hole in the reordered array. For example, if the array originally contained 0,1,2 it should contain the combination of these three numbers only and not incremented values like 3 or 4.
c.) After the reordering, the values should all be between the original minimum (always 0) and the maximum values.
Thanks in advance,
Arya.
[1204 byte] By [
aryasanyal] at [2007-9-30 12:36:16]
Unless you really need an array, this would be easy with something like a LinkedList. Simply find the value you want to change to and remove it, then insert the value at the appropriate index, and the rest of the list will take care of itself. You could use Integers instead of primatives.
If you really want to stay with an array, I would advise using System.arraycopy to shift a portion of the array. Store the value you are removing, arraycopy to shift from where you want to place the value, then place the value.private static void change(int[] array, int oldVal, int newVal) {
int numElements = array.length;
int oldNdx = 0;
int newNdx = 0;
// find the index of the values you want to change
for(;oldNdx < numElements && array[oldNdx] != oldVal; oldNdx++)
;
for(;newNdx < numElements && array[newNdx] != newVal; newNdx++)
;
// make sure indeces are valid
if (oldNdx == numElements) {
throw new IllegalArgumentException(oldVal + " not in array");
}
if (newNdx == numElements) {
throw new IllegalArgumentException(newVal + " not in array");
}
// no change
if (oldNdx == newNdx) {
return;
}
// which way to shift areas of array between changed places
int shiftDir = newNdx < oldNdx ? 1 : -1;
System.arraycopy(array, newNdx, array, newNdx + shiftDir, Math.abs(newNdx - oldNdx));
array[newNdx] = oldVal;
}
Well, I have certain integer ids stored in a table. The user can modify any of the ids. If he modifies them, then based on the value of the new id (ie., whether it is increased or decreased), the other values in the column will have to be modified such that they retain their ascending order sequence only incorporating the value that has been newly changed.
Thus in the example sequence 0,1,2, if 2 is changed to 0, then the other two get pushed up by one but maintain their ascending sequence. Thus it becomes 1,2,0 after the reordering.
> Sounds like a homework assignment... if that is not correct, then what is such an algorithm practical for?
Well, it comes in very handy when doing a LUP (Lower Upper Permutation) decompostion of a full rank
matrix. Agreed, algorithmically it isn't much; suppose q[x] contains a permutation, the following snippet
builds the inverse permutation p (given two arrays p and q of equal length) - for (int x= 0; x < q.length; i++)
p[q[x]]= x;
Both arrays p and q are sufficient to permute and 'inverse-permute' any sequence of objects ...
kind regards,
Jos
JosAH at 2007-7-4 16:26:44 >
