CODEWITHSUNDEEP
c#.netalgorithmlinq
Colonel Panic
Colonel Panic

Reputation: 137682

How to sort a list, saving map from old positions to new positions?

I'd like to sort a list, and save a map from the old positions of the elements to their new positions?

For example, if the list to sort were 

var words = "once upon a midnight dreary".Split();
// once upon a midnight dreary

Then the sorted list would be 

var orderedWords = words.OrderBy(w => w).ToArray();
// a dreary midnight once upon

Then because 'once' moved from position 0 to position 3, the map would be 

0 => 3, 1 => 4, 2 => 0, 3 => 2, 4 => 1

So that, for all i

words[i] = orderedWords[map[i]]

How can I do this? I expect it should be possible in the same time complexity as ordinary sorting, ie. O(n log n)

I tried: 

var map = words.Select((word, index) => new { Word = word, Index = index}).OrderBy(x => x.Word).Select(x => x.Index);

But this gives 

> 2, 4, 3, 0, 1

Which fails the identity I gave above

for(int i = 0; i < words.Length; i++)
    Assert.AreEqual(words[i], orderedWords[map[i]]);

Upvotes: 3

Views: 394

Answers (1)

Tim Schmelter
Tim Schmelter

Reputation: 460238

You have to use the new index after the OrderBy:

var map = words
    .Select((word, index) => new { Word = word, Index = index })
    .OrderBy(x => x.Word)
    .Select((x, NewIndex) => new { x.Word, x.Index, NewIndex });

Result:

[0] { Word = "a", Index = 2, NewIndex = 0 } 
[1] { Word = "dreary", Index = 4, NewIndex = 1 }    
[2] { Word = "midnight", Index = 3, NewIndex = 2 }
[3] { Word = "once", Index = 0, NewIndex = 3 }  
[4] { Word = "upon", Index = 1, NewIndex = 4 }

Update: acc. comment: "how do I get the 'old index to new index' data structure out?"

You could use a Dictionary:

var map = words
    .Select((word, index) => new { Word = word, OldIndex = index })
    .OrderBy(x => x.Word)
    .Select((x, NewIndex) => new { x.Word, x.OldIndex, NewIndex })
    .ToDictionary(x => x.OldIndex, x => x.NewIndex);

for (int i = 0; i < words.Length; i++)
{
     Console.WriteLine("Word: {0} \tOldIndex: {1} \tNewIndex: {2}", words[i], i, map[i]);
}

Result:

Word: once      OldIndex: 0     NewIndex: 3
Word: upon      OldIndex: 1     NewIndex: 4
Word: a         OldIndex: 2     NewIndex: 0
Word: midnight  OldIndex: 3     NewIndex: 2
Word: dreary    OldIndex: 4     NewIndex: 1

Upvotes: 3

Related Questions