元組列表的所有組合

Question

我在練習一些優化問題，並且卡住了。

我有一個元組列表和我做了以下內容：

private static int CalculateMinimumTotalCost(List<Tuple<int, int>> tuples) 
{ 
    int minimumCost = 0; 

    for(int i=0;i<tuples.Count()-1;i++) 
    { 
     minimumCost += Math.Max(Math.Abs(tuples[i].Item1 - tuples[i + 1].Item1), Math.Abs(tuples[i].Item2 - tuples[i + 1].Item2)); 
    } 
    return minimumCost; 
} 

的想法是，給定一個元組列表和這個數學公式，我需要找到成本最低。問題在於元組的順序可以重新排列。我的工作是找到元組的最低成本安排。

所以我想要做的是循環所有可能的元組組合，並以最小的成本返回組合。

例如：

（1,2）（1,1）（1,3）= 3

（1,1）（1,2）（1,3）= 2

所以在這種情況下，我會返回2，因爲這種安排成本較低。

我明白，當有N個元組時，組合的數目是N !.

如何獲取元組列表的所有可能組合？

謝謝！

Answer 1

至於其他的建議，你應該創建Point類：

public partial class Point 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 

    public Point(int x, int y) 
    { 
     this.X = x; 
     this.Y = y; 
    } 
} 

而且，我們的封裝用於計算距離和總成本的功能：

public partial class Point 
{ 
    public static int CalculateDistance(Point p0, Point p1) 
    { 
     return Math.Max(
      Math.Abs(p0.X - p1.X), 
      Math.Abs(p0.Y - p1.Y) 
      ); 
    } 
} 

public static class PointExtensions 
{ 
    public static int GetTotalCost(this IEnumerable<Point> source) 
    { 
     return source 
      .Zip(source.Skip(1), Point.CalculateDistance) 
      .Sum(); 
    } 
} 

最後，將需要另一種擴展方法來創建「所有可能的組合」：

public static class PermutationExtensions 
{ 
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> source) 
    { 
     if (source == null || !source.Any()) 
      throw new ArgumentNullException("source"); 

     var array = source.ToArray(); 

     return Permute(array, 0, array.Length - 1); 
    } 
    private static IEnumerable<IEnumerable<T>> Permute<T>(T[] array, int i, int n) 
    { 
     if (i == n) 
      yield return array.ToArray(); 
     else 
     { 
      for (int j = i; j <= n; j++) 
      { 
       array.Swap(i, j); 
       foreach (var permutation in Permute(array, i + 1, n)) 
        yield return permutation.ToArray(); 
       array.Swap(i, j); //backtrack 
      } 
     } 
    } 
    private static void Swap<T>(this T[] array, int i, int j) 
    { 
     T temp = array[i]; 

     array[i] = array[j]; 
     array[j] = temp; 
    } 
} 

從Listing all permutations of a string/integer源，適於更LINQ友好

---

用法：

void Main() 
{ 
    var list = new List<Point> 
    { 
     new Point(1, 2), 
     new Point(1, 1), 
     new Point(1, 3), 
    }; 

    // result: Point[] (3 items) : (1, 1), (1, 2), (1,3) 
    list.GetPermutations() 
     .OrderBy(x => x.GetTotalCost()) 
     .First(); 
} 

---

編輯：由於@EricLippert指出，source.OrderBy(selector).First()有一些額外開銷。這下面這個問題擴展方法處理：

public static class EnumerableExtensions 
{ 
    public static T MinBy<T, TKey>(this IEnumerable<T> source, Func<T, TKey> keySelector, IComparer<TKey> comparer = null) 
    { 
     IEnumerator<T> etor = null; 

     if (source == null || !(etor = source.GetEnumerator()).MoveNext()) 
      throw new ArgumentNullException("source"); 

     if (keySelector == null) 
      throw new ArgumentNullException("keySelector"); 

     var min = etor.Current; 
     var minKey = keySelector(min); 

     comparer = comparer ?? Comparer<TKey>.Default; 
     while (etor.MoveNext()) 
     { 
      var key = keySelector(etor.Current); 
      if (comparer.Compare(key, minKey) < 0) 
      { 
       min = etor.Current; 
       minKey = key; 
      } 
     } 

     return min; 
    } 
} 

而且，我們可以重寫上面的解決方案爲：

list.GetPermutations().MinBy(x => x.GetTotalCost()) 

Answer 2

您可以將for循環更改爲Foreach，以使其更具可讀性，而不是使用索引來獲取值。

private static int CalculateMinimumTotalCost(List<Tuple<int, int>> tuples) 
     { 
      int minimumCost = 0; 
      Tuple<int, int> currentTuple = tuples.First(); 

      foreach (Tuple<int, int> tuple in tuples) 
      { 
       minimumCost += Math.Max(Math.Abs(currentTuple.Item1 - tuple.Item1), Math.Abs(currentTuple.Item2 - tuple.Item2)); 
       currentTuple = tuple; 
      } 
      return minimumCost; 
     }