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.

Lahnda

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.

Balas

Great stuff, I appreciate your help. It's pretty obvious now that I'm looking at it ... But what about an Iteration, how is it different from an Enumeration ? – Lahnda

@DimitarDimitrov Enumeration and iteration in this context are very closely related: enumeration means producing all permutations, while iteration means going through them in a loop. To enumerate a sequence you need to know how to do it; to iterate it you need to actually do it. In the context of C#, one could enumerate a sequence by providing an IEnumerabl<T> with deferred execution. Then he would have a choice to iterate that sequence, say, with a foreach loop, or do something else - say, taking the first few elements, and throwing away the rest of the enumeration. – Balas

So just to summarize, enumeration is the act of "producing" a sequence of permutations and iteration is the act of "going through the sequence" ? Furthermore differed execution is basically "knowing how to enumerate and doing it upon request" not necessary upfront ? – Lahnda

@DimitarDimitrov Yes, that's close enough. "Producing" does not necessarily mean producing the sequence in the memory, though, so you could "produce" a sequence by providing a pair of HasNext and GetNext methods to the caller. – Balas

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.

Procurator

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;
}

Haerr

This helped a lot ! I wish I can accept 2 answers ... Or at least up vote more than once ! – Lahnda