用LINQ/.NET4解决组合问题

如果您有权访问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

首先,最后一点(关于 i9 )没有必要,因为 全部的

我不认为你能显著改进这个查询。。。它实际上已经相当有效了,因为每一步都比前一步有更少的可能组合。

您可以轻松地对一些代码进行分解,以使查询更具可读性。例如,使用一个谓词检查每一步的算法不变性,并使用一个助手从数字中构建数字(而不是“内联”乘法和加法)。

Dn公司 N ,和 Xn 数字由D1…Dn组成。在每个步骤N中,以下语句应为真:

• Dn不在[D1…D(n-1)]
• Xn可被N整除

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

还是挺大的,但比原版可读性强多了。。。