Solving combination problems with LINQ / .NET4

Question

I saw this article appearing on my MSDN RSS feed, and after reading it and the article published here . I began to wonder about the solution.

The rules are simple:

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

• The number must be divisible by 9.
• If the rightmost digit is deleted, the remaining number must be divisible by 8.
• If the rightmost digit of the new number is deleted, the remaining number must be divisible by 7.
• And so on, until there is only one digit (which will necessarily be divided by 1).

This is his suggested monster LINQ query:

// C# and LINQ solution to the numeric problem presented in:
// http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/

int[] oneToNine = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// the query
var query = 
    from i1 in oneToNine
   from i2 in oneToNine
    where i2 != i1
       && (i1 * 10 + i2) % 2 == 0
    from i3 in oneToNine
    where i3 != i2 && i3 != i1
       && (i1 * 100 + i2 * 10 + i3) % 3 == 0
    from i4 in oneToNine
    where i4 != i3 && i4 != i2 && i4 != i1
       && (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
    from i5 in oneToNine
    where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
       && (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
    from i6 in oneToNine
    where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
       && (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
    from i7 in oneToNine
    where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
       && (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
    from i8 in oneToNine
    where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
       && (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 + 
           i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
    from i9 in oneToNine
    where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
    let number = i1 * 100000000 +
                 i2 * 10000000 +
                 i3 * 1000000 +
                 i4 * 100000 +
                 i5 * 10000 +
                 i6 * 1000 +
                 i7 * 100 +
                 i8 * 10 +
                 i9 * 1
    where number % 9 == 0
    select number;

// run it!
foreach (int n in query)
    Console.WriteLine(n);

Octavio : " , ", , . ? , .NET4, , , . LINQ, , .NET4 ( ++, # .. ).

Answer 1

ImmutableList, . , , . , , .

Dim query = From i1 In Tuple.Create(0L, allNums).ChooseNextNumber(1)
            From i2 In i1.ChooseNextNumber(2) _
            From i3 In i2.ChooseNextNumber(3) _
            From i4 In i3.ChooseNextNumber(4) _
            From i5 In i4.ChooseNextNumber(5) _
            From i6 In i5.ChooseNextNumber(6) _
            From i7 In i6.ChooseNextNumber(7) _
            From i8 In i7.ChooseNextNumber(8) _
            From i9 In i8.ChooseNextNumber(9)
            Select i9.Item1

<System.Runtime.CompilerServices.Extension()> _
Private Function ChooseNextNumber(
      ByVal previous As Tuple(Of Integer, ImmutableList(Of Integer)),
      ByVal modulusBase As Integer) _
    As IEnumerable(Of Tuple(Of Integer, ImmutableList(Of Integer)))
    Return From i In previous.Item2
           Let newTotal = previous.Item1 * 10 + i
           Where newTotal Mod modulusBase = 0
           Select Tuple.Create(newTotal, previous.Item2.Remove(i))
End Function

Answer 2

, -, ( i9) , 1-9 9...

Answer 3

, ... , , .

, , - , . , , , ( "" ).

Dn N, Xn D1... Dn. N :

• Dn [D1... D (n-1)]
• Xn N

In the following code, this invariant is implemented by the delegate isValid:

// Delegate with variable number of arguments
delegate TResult FuncWithParams<TArg, TResult>(params TArg[] args);

void Main()
{

    var oneToNine = Enumerable.Range(1, 9).ToArray();

    // Creates a number from its digits
    FuncWithParams<int, int> makeNumber =
        digits => digits.Aggregate(0, (acc, d) => acc * 10 + d);

    // Checks the invariant against a sequence of digits
    FuncWithParams<int, bool> isValid =
        digits => !digits.Take(digits.Length - 1).Contains(digits.Last())
                && makeNumber(digits) % digits.Length == 0;

    var query = 
        from d1 in oneToNine
        from d2 in oneToNine
        where isValid(d1, d2)
        from d3 in oneToNine
        where isValid(d1, d2, d3)
        from d4 in oneToNine
        where isValid(d1, d2, d3, d4)
        from d5 in oneToNine
        where isValid(d1, d2, d3, d4, d5)
        from d6 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6)
        from d7 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7)
        from d8 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7, d8)
        from d9 in oneToNine
        where isValid(d1, d2, d3, d4, d5, d6, d7, d8, d9)
        select makeNumber(d1, d2, d3, d4, d5, d6, d7, d8, d9);

    query.Dump();
}

Still quite large, but much more readable than the original ...