使用LINQ/.NET4解决组合问题

Question

我在我的 MSDN RSS 订阅中看到了这篇文章，链接在此：this article，阅读后，我开始思考这个问题。这里是引用的文章。

规则很简单：

找到一个包含 9 个数字且每个数字都只出现一次的数字。该数字必须满足以下可整除性要求：

1. 数字应该被 9 整除。
2. 如果删除最右边的数字，则剩余数字应该能被 8 整除。
3. 如果删除新数字的最右边的数字，则剩余数字应该能被 7 整除。
4. 以此类推，直到只剩下一个数字（必定能被 1 整除）。

这是他提出的 monster LINQ 查询：

// 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中（托管c ++，C＃等都可以接受）。

- slf

---

这让我的眼睛很疼。LINQ并不是解决所有问题的万能药...！ - Noldorin

@Noldorin，虽然不是所有问题都适用于LINQ，但它非常适合解决这个问题... 你愿意写一个非LINQ的解决方案吗？我敢打赌它不会更清晰 ;) - Thomas Levesque

请提供一种易于阅读且性能相等或更好的非Linq解决方案。 - slf

@Thomas：我可以想出十几种方法来让它更清晰明了... :) 抱歉，目前没有时间进行这样的努力！希望其他人能够证明这一点。 - Noldorin

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

- Gideon Engelberth

---

尽管我不喜欢VB的语法，但这是非常优雅的解决方案...点赞! - Thomas Levesque

Answer 2

我认为你无法显著改进这个查询...它已经相当高效了，因为每个步骤的可能组合比前一个步骤少得多。

你可以轻松地将一些代码因式分解，使查询更易读。例如，使用一个谓词来检查每个步骤的算法不变量，以及一个帮助程序从数字中构建数字（而不是“内联”乘法和加法）。

让我们称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();
}

仍然很大，但比原来更易读...

- Thomas Levesque

---

这种方式更易于阅读，但它是否真的更高效呢？ - slf

不是的。实际上，我认为由于委托调用的开销，它可能比原始实现稍微慢一些，但差异可能不足以注意到。 - Thomas Levesque

Answer 3

首先，最后一位关于i9的部分是不必要的，因为所有1-9的排列都可以被9整除...

- BlueRaja - Danny Pflughoeft