Enumeration vs Indexing vs Iteration

Question

I've been reading Eric Lippert's blog for a while now (it's excellent, you should check it out) and In the comments of one of his posts, he mentions that he had no intention indexing a sequence of numbers but rather only enumerate them.

What is the difference between enumeration and indexing, I've searched everywhere ? During my searches I've become even more confused when Iteration was brought into the equation ? Can someone please explain those 3 concepts, maybe even throw in an example ? Before you mark this as a dupe, I've already seen some questions on "Iterator vs Enumerator", however I've yet so see a proper explanation (hence the question). I appreciate your help.

Answer 1

In the comment to the article Eric replied to an observation that since the size of a permutation grows exponentially, it would quickly outgrow numbers representable with 32 bits. Eric's reply was that he has no intention of indexing permutations, by which he meant defining a numbering scheme to obtain a sequential number of a permutation. That is why, he said, overflowing 32 bits was not one of his concerns: his approach allowed to enumerate, or simply "produce", all permutations in some order, as opposed to providing a way to get N-th permutation according to some numbering scheme.

Contrast this to a problem discussed in a question about producing N-th permutation without going through all the preceding ones: here, the author wants to index, or give numbers to, permutations, so the size of an integer is of a concern to them.

Here is an example of indexing permutations discussed in the question linked above:

1 ABC
2 ACB
3 BAC
4 BCA
5 CAB
6 CBA

This indexing scheme lets you answer two questions:

• What is the number of a particular permutation, say, BCA? (it's 4)
• What is permutation number X, say, 5? (it's CAB)

This problem could be somewhat harder than enumerating all permutations, because you need to produce a numbering scheme.

Answer 2

Conceptually, both enumerators and iterators know little about a sequence. They usually can:

• Fetch next item
• Check if current element is the last one

They may behave differently when a collection is modified. These types are useful to work with large amount of data, steams, LINQ and lazy loading, as they fetch one element at a time. To fetch an i element from a sequence you have to iterate through all previous elements, this is an O(N) operation. You can think about them as a linked list data structure.

Indexers only work with fixed-length memory, even though underlying storage may shrink and grow (like in a List<T> type). Indexers know what is the type of data, and how much it take storage, or how much a reference to the object take storage. This allows indexers to fetch any item from the sequence in O(1), the down side is that you must store all the data in-memory. It simply multiplies the index by the size of the element and adds the result to the start address - hence it gets a value or reference to needed object. You can think about indexers as an array data structure.

Answer 3

You can only index things, that are real. You can index an array using operator [] or you can index a list (in C# at least, people that are into more formal computer science will cringe).

You cannot index an IEnumerable<T> because to enumerate simple means that you can go through all items in order. But you cannot jump to a specific item.

string text = "hello";

This is enumerating:

foreach( var c in text ) Console.WriteLine(c);

This uses indexing:

for( int i = 0 ; i < text.Length ; i++ ) Console.WriteLine(text[i]);

This is real data:

var arr = new int[15]; 

This is not real, there's no data in number, just a promise to deliver data on enumeration. You will need to materialize it to have real data:

var number = GetNumbers();

This will produce an endless number of ones. It's not real data, it's kind of a recipe how to produce real data once you enumerate it:

public IEnumerable<int> GetNumbers()
{
    while(true) yield return 1;
}