Решение проблем с LINQ/.NET4

Question

Я увидел this article всплывающее окно в моем RSS-канале MSDN, и после прочтения его, and the sourced article here Я начал задаваться вопросом о решении.

Правила просты:

Найти номер, состоящий из 9 цифр, в которых каждая из цифр от 1 до 9, появляется только один раз. Это число должно удовлетворять этим требованиям делимости:

1. число должно быть кратно 9.
2. Если правая цифра удаляется, оставшееся число должно быть кратно 8.
3. Если крайняя правая цифра новый номер удаляется, оставшееся число должно делиться на 7.
4. И так далее, пока не будет только одна цифра (которая обязательно будет делиться на 1).

Это его предложил монстр 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); 

Октавио гласит: «Обратите внимание, что ни одна попытка вообще не было сделано, чтобы оптимизировать код», что я хотел бы знать, что если мы DID пытается оптимизировать этот код. Это действительно лучший способ получить этот код? Я хотел бы знать, как мы можем сделать это лучше всего с .NET4, в частности, делая так же параллельно, насколько это возможно. Я не обязательно ищу ответ в чистом LINQ, предполагаю, что .NET4 в любой форме (управляемый C++, C# и т. Д. Все приемлемо).

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, следующие инструкции должны быть верно:

• Дн не в [D1, ... D (п-1)]
• Х делится на 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(); 
} 

еще довольно большой, но гораздо более читабельным, чем оригинал ...