Enumeration produces a collection’s elements in sequence. The sequence may already be represented by a data structure, or an algorithm may generate it: every combination or permutation of a set of positions, for example. In the latter case, the order of generation can be part of the problem. section 2.2 section 6.2.4
The cost depends on what must happen to produce the next element:
- An immutable stack can enumerate n items by repeatedly checking IsEmpty, reading Peek, and advancing with Pop. These operations are constant-time, giving O(n) time and O(1) extra memory apart from the enumerator. section 2.2
- An immutable queue built from two stacks also takes O(n) time to enumerate n items, but reversing one stack can require O(n) extra memory. section 2.4
- For combinations of arbitrary items, enumerate combinations of integer positions first, then use those positions as indices into the items. The same separation works for permutations. section 6.3
Positions before values
Given ["ham", "jam", "spam", "lamb"], the position combination [1, 2] selects "jam" and "spam". One enumeration of position combinations can therefore be applied to lists of different element types. section 6.3
Listing 6.15 Producing a combination of any list
static class Extensions
{
public static IList<T> Combine<T>(
this IList<T> items, IList<int> combination)
{
var result = new T[combination.Count];
for (int i = 0; i < combination.Count; i += 1)
result[i] = items[combination[i]];
return result;
}
}
The C# Combine method makes the separation concrete: it walks the supplied positions and copies the corresponding items into a result array. section 6.3
Sometimes merely producing every result is insufficient. In change-ringing permutation enumeration, each successive ordering must differ by one swap of adjacent elements; lexicographic order does not satisfy that restriction. A recursive C# iterator generates the required order by inserting each new element at positions traversed in alternating directions. section 6.2.4
Listing 6.12 A recursive change-ringing algorithm
static IEnumerable<IEnumerable<int>> Changes(int n)
{
if (n == 0) #1
{
yield return [];
yield break;
}
bool fromLeft = false; #2
foreach (var perm in Changes(n - 1))
{
for (int row = 0; row < n; row += 1)
yield return perm.InsertAt(fromLeft ? row : n-row-1, n-1);
fromLeft = !fromLeft; #3
}
}
static class Extensions
{
public static IEnumerable<T> InsertAt<T>(
this IEnumerable<T> items, int index, T insert)
{
int current = 0;
foreach (T item in items)
{
if (current == index)
yield return insert;
yield return item;
current += 1;
}
if (current == index)
yield return insert;
}
}
The Changes iterator shows how alternating insertion direction turns a recursive permutation generator into a constrained enumeration. section 6.2.4
