Complicated Iteration

[jemidiah]

Does .NET have built-in techniques for more complicated forms of iteration like the following:

1. Iterate over rearrangements of a list.
2. Iterate over subsets of a list.
3. Iterate over all indexes of a multidimensional list.
4. Iterate over all "combinations" of a list, i.e. all subsets of a list of a given length, where subsets that differs only in their ordering occur only once total.

I recently had cause to do (1) and my method was ugly, slow, tedious, and generalized poorly, which is why I ask. I can think of better ways, but it was garbage code anyway [brute force checking that there are precisely 576 seven-digit numbers made up of 1, 2, 3, 4, 5, 6, and 7 that are also divisible by 11]. The others are just for my own curiosity.

[Shaggy Hiker]

There is lots that can be done with LINQ, but I have come to doubt that just because you can come up with a single LINQ statement that replaces a fairly convoluted loop, it is a good idea. There are times that LINQ is quite efficient, such as when joining two data sources (not a Datasource, but two sources of data....all the good names have a meaning). LINQ can certainly create subsets of lists, so it will accomplish some interpretations of item #2.

Iterating over all items in a multidimensional array can be done with a For Each loop, but if you meant something like an List (of List (of T)), then that would not apply.

I seriously doubt that there is any efficient way to accomplish #4 for any general case.

[jemidiah]

I've never used LINQ, though I've heard about it off-and-on. If it's simple, could you give an example of iterating over subsets of a list?

[ThomasJohnsen]

1. and 2. can be done relatively compact in several variants:

(Will perform various actions on a typed List(Of Integer) and display results in ListBoxN, N = {1, 2, 3})

Private Sub TestLoopingOfTypedLists()
 
        Dim MyList As New List(Of Integer)
 
        MyList.AddRange(New Integer() {1, 7, 3, 9, 2, 11, 19, 6, 3, 1, 12})
 
        '1. Iteration over a rearrangement
        MyList.OrderByDescending(Function(n) 20 - n).ToList().ForEach(AddressOf DoSomethingA)
 
        '2. Iterate over subsets of a list.
        MyList.Distinct.ToList.ForEach(AddressOf DoSomethingB)
        MyList.Where(Function(n) n > 5).ToList.ForEach(AddressOf DoSomethingC)
 
    End Sub
 
    Private Sub DoSomethingA(ByVal sInteger As Integer)
        ListBox1.Items.Add(sInteger.ToString)
    End Sub
    Private Sub DoSomethingB(ByVal sInteger As Integer)
        ListBox2.Items.Add(sInteger.ToString)
    End Sub
    Private Sub DoSomethingC(ByVal sInteger As Integer)
        ListBox3.Items.Add(sInteger.ToString)
    End Sub

Tom

[Shaggy Hiker]

I would use LINQ to get the subset of a list. As an example:

Dim subset = (From m In mMarkGroups Where m.AUID = AUID AndAlso m.MSID = MSID)

This is taken from something I am working on. Roughly speaking, the whole thing is a matrix with AU on one axis and MS on a different axis. An AUID is the ID for an AU, while you can probably figure out what an MSID would be. Each node in the matrix is a MarkGroup, so what this line does is return the set of MarkGroups that have the desired AUID and MSID. Since those IDs would be unique, what this is actually doing is returning only a single Mark Group. This line was taken from a function that took AUID and MSID as arguments, so the function was a way to get a single node from the matrix.

You can extend that a bit further by adding a select:

(From m In mMarkGroups Where m.AUID = AUID AndAlso m.MSID = MSID Select m.NumberOfFish).Sum

The initial line would return a List (of MarkGroup), though because of the way the collection was set up, that would be a list that only had one member. Had I searched on just AUID or just MSID, I would be returning a set of MarkGroup, which would be either a row or a column in the matrix. In this second example, I am specifically getting the NumberOfFish member from each item in the list. If I left off the .Sum part, what I would be getting would be a List (of Integer), because I was selecting an integer member from the items in the list. It would still be a list with only one member, since the WHERE clause is still selecting for only a single node in the matrix.

By adding the .Sum, I am now getting just an Integer. It isn't a list anymore. Instead, the .Sum adds up the integers in the list and returns the sum. In this case, since the WHERE clause will restrict the return to just one node in the matrix, that single integer is not all that interesting, but if I had just an AUID or just an MSID, such that the return was a single row or column from the matrix, then the .Sum would start being more meaningful, since it would be the sum of the row or the column.

Having said that, I should also add that this is a pretty poor and trivial example. The same code could have been written like this:

Dim cnt as Integer
For Each mg As MarkGroup in mMarkGroups
 If mg.AUID = AUID AndAlso mg.MSID= MSID Then
  cnt += mg.NumberOfFish
 End If
Next

That loop was replaced by the single line of LINQ, which is what makes LINQ look so appealing. However, the loop would run faster. LINQ performs worse than a simple loop in those cases where a simple loop would work. It takes less typing to write, it just isn't as fast. There are times when LINQ is faster, though, but you do have to keep in mind that it isn't the solution to every problem.

As for a subset, you could write something odd like this:

For Each mg As MarkGroup In (From m in mMarkGroups WHERE m.AUID = AUID)
 'Do something
Next

What that would do would be to iterate through all members of the subset of mMarkGroups that matched the condition in the WHERE clause. I can't really take that much further, though, because I can't think of where to take it. Effectively, the .Sum was iterating through all the members in a subset and adding them, and you can do the same kind of thing yourself if you choose to, but you have to keep in mind that just because you CAN do so, it still might not be all that effective.