How to exchange the items of enumeration by interating only once?

Question

I'm trying to exchange the ordering of particular items of an IEnumerable.

Given an IEnumerable<int> a; of the elements:

1, 2, 3, 4, 5

and what I want to do is write a exchange iterator which resulting a.Exchange(1, 2) in:

1, 3, 2, 4, 5

But I don't want the enumerable be iterated more than once with this simple purpose. What I have so far is:

public static IEnumerable<T> Exchange<T>(
    this IEnumerable<T> source, int index1, int index2) {
    var i=0;

    foreach(var y in source) {
        if(index1==i) {
            var j=0;

            foreach(var x in source) {
                if(index2==j) {
                    yield return x;
                    break;
                }

                ++j;
            }
        }
        else {
            if(index2==i) {
                var j=0;

                foreach(var x in source) {
                    if(index1==j) {
                        yield return x;
                        break;
                    }

                    ++j;
                }
            }
            else {
                yield return y;
            }
        }

        ++i;
    }
}

Here's a assumption that index1 and index2 wouldn't exceed the elements of the enumerable. The code done the work of exchange(the ordering) in most cases, but it does iterate more than once. Note index1 and index2 might not be the real indices of source, they would be the Mth and Nth element when the enumeration occurs.

ToArray or ToList may also increase the times of iteration.

Answer 1

WOLOG assume that index1 is less than index2.

Make your own enumerator; don't use foreach.

For elements up to index1, iterate normally and yield each.

Then when you hit index1, allocate an array big enough to hold the elements between index1 through index2 -- that is, including the index1th element, but not the index2th element.

Read the elements into that array using your enumerator.

Now read the index2th element and yield it.

Your enumerator is now set to one beyond index2.

Now yield everything in the array except the index1th element.

Then yield the index1th element.

Then yield the rest of the elements normally.

Don't forget to call Dispose on the enumerator when you're done.

Answer 2

The easiest way is probably something like this:

public static IEnumerable<T> Exchange<T>(
    this IEnumerable<T> source, int index1, int index2) 
{
    return source.Select((x, i) => new { x, i })
                 .OrderBy(p => p.i == index1 ? index2 : p.i == index2 ? index1 : p.i)
                 .Select(p => p.x);
}

new[] { 1, 2, 3, 4, 5 }.Exchange(1, 2); // { 1, 3, 2, 4, 5 }

To do it without an OrderBy, I think it would look something like this:

public static IEnumerable<T> Exchange<T>(
    this IEnumerable<T> source, int index1, int index2) 
{
    if (index1 > index2)
    {
        int x = index1;
        index1 = index2;
        index2 = x;
    }

    int index = 0;
    List<T> itemsBetweenIndexes = new List<T>();
    bool betweenIndexes = false;
    T temp = default(T);
    foreach(var item in source)
    {
        if (!betweenIndexes)
        {
            if (index == index1)
            {
                temp = item;
                betweenIndexes = true;
            }
            else
            {
                yield return item;
            }
        }
        else
        {
            if (index == index2)
            {
                betweenIndexes = false;
                yield return item;
                foreach(var x in itemsBetweenIndexes)
                {
                    yield return x;
                }
                itemsBetweenIndexes.Clear();
                yield return temp;
            }
            else
            {
                itemsBetweenIndexes.Add(item);
            }
        }

        index++;
    }
}

Initially, this loops through looking for the item at index1 yielding every item until it finds it. Once found it begins adding items to an internal queue until it finds index2. At that point it yields the item at index2, followed by every item in the queue, in order, followed by the item at index1. It then goes back to looking for index1 (which it won't find) until it reaches the end of the list.

Answer 3

In order to perform this operation without iterating the original more than once, you would need to store the content of the subsequence between the indexes that you are swapping.

Here is how you can implement the algorithm (I renamed index1 and index2 to smallerIndex and greaterIndex):

using (IEnumerator<T> e = source.GetEnumerator()) {
    IList<T> saved = new List<T>(greaterIndex-smallerIndex+1);
    int index = 0;
    while (e.MoveNext()) {
        // If we're outside the swapped indexes, yield return the current element
        if (index < smallerIndex || index > greaterIndex) {
            index++;
            yield return e.Current;
        } else if (index == smallerIndex) {
            var atSmaller = e.Current;
            // Save all elements starting with the current one into a list;
            // Continue until you find the last index, or exhaust the sequence.
            while (index != greaterIndex && e.MoveNext()) {
                saved.Add(e.Current);
                index++;
            }
            // Make sure we're here because we got to the greaterIndex,
            // not because we've exhausted the sequence
            if (index == greaterIndex) {
                // If we are OK, return the element at greaterIndex
                yield return e.Current;
            }
            // Enumerate the saved items
            for (int i = 0 ; i < saved.Count-1 ; i++) {
                yield return saved[i];
            }
            // Finally, return the item at the smallerIndex
            yield return atSmaller;
            index++;
        }
    }
}

Demo on ideone.

Answer 4

You could do it in one pass by creating a List<T> and then returning it as an IEnumerable<T> type:

public static IEnumerable<T> Exchange<T>(this IEnumerable<T> source, int index1, int index2)
{
    // TODO: check index1 and index2 are in bounds of List/Enumerable
    var result = source.ToList(); // single enumeration
    // Swap vars
    var temp = result[index1];
    result[index1] = result[index2];
    result[index2] = temp;
    return result;
}