元组列表的所有组合

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