# Rearrange string to an anagram of the string - get new position, old position values

I'm writing a function to take an anagram pair (words or phrases spelled with the same letters) and determine how you could move the letters to change one into the other.

The results would be something like this:

[[0, 1], [1, 6], [2, 0], [3, 4], [4, 2], [5, 5], [6, 3]]


The character in the 0 (a) position moves to 1, the character in position 1 (d) moves to 6, etc. I've already successfully solved this but perhaps there's a better way!

Language of choice (required!) is javascript. Here's my current, working function:

function _get_new_positions(source, target) {
// convert both strings to arrays - uppercase so we can find the destination
// spot without worrying about cases
source = source.toUpperCase().split('');
target = target.toUpperCase().split('');

var transform = [];
var repeated = [];
var found = 0;

for(var i=0; i<source.length; i++) {
// keep track of how many times we've found and 'moved' this letter
repeated[source[i]] = repeated[source[i]] ? repeated[source[i]] + 1 : 1;
found = 0;
want  = repeated[source[i]];
for(var j=0; j<target.length; j++) {
if( target[j] == source[i] ) {
found++;
console.log('found is ' + found);
if( found == want ) {
transform.push([i,j]);
break;
}
}
}
}
return transform;
}


You can simplify the logic by setting each character you find in target to NULL. I also like to use a "while" loop as shown below.

function _get_new_positions(source, target) {
var transform = [], i, j, found, want;
// convert both strings to arrays - uppercase so we can find the destination without worrying about cases
source = source.toUpperCase().split('');
target = target.toUpperCase().split('');
for(i=0; i<source.length; i++) {
j = 0;
found = false;
want  = source[i];
while((j < target.length) && !(found = (target[j] == want))){j++}
if (! found) {
console.log("Cannot find character: " + want + " at [i]: " + i);
} else {
console.log("Found character: " + want + " at [i,j]: " + i + j);
target[j] = ''; //blank out the character for future searches
transform.push([i,j])
}
}
return transform;
}

• That's a nice improvement over my original design, thanks :-) – Erik Jul 13 '11 at 0:59

It can be simplify by not converting to array using charAt, also using replace to perform the second loop and erasing found matches. Also, the return value can be reduced to an array of ints since the array index tracks the position in the source.

function _get_new_position (source, target){
source = source.toUpperCase()
target = target.toUpperCase();

var result = []
, l      = target.length;

while(l--){ // Starting from the end, swaps doubled letters index
target = target.replace( source.charAt(l)         //
, function (char, index){  // charAt, index
result.unshift(index); // Add the found offset inverted
return ' ';            // Suppress the char in source
});
}
return result;
}