程序員的組合？

我開始編寫一個C＃Silverlight程序，試圖找到旅行銷售人員問題的蠻力解決方案。但一直試圖找出所有可能的路線。程序員的組合？

對於我的程序，我生成隨機點並試圖找到可以加入它們的最短行，而不必訪問任何兩次。

因此，如果我有三個點A，B，& CI想要找到A，B，& C的所有不同組合，其中每個僅用於一次，並且該集合與已經找到的另一個集合不相同當逆轉時。

如： ABC ACB BAC

但我怎麼可以計算任意數量的點的所有組合？

我正在寫這個程序的樂趣，我現在更感興趣的是找到一個很好的資源，以瞭解如何解決編程中的組合問題。我發現學習combinatorics的所有內容都告訴我如何找到可能的組合數，並且對於實際枚舉所有可能的組合沒有用處。

來源

2012-01-10 user802599

這是排列得，順便說一句。谷歌「得到列表的所有排列」，你會發現很多結果。 – Ryan 2012-01-10 04:26:38

還沒有找到答案，我已經搜索了互聯網，我的大學圖書館，並與我的大學的數學教授交談。我沒有找到這個http://bytes.com/topic/c/answers/536779-richard-heathfields-tsp-permutation-algorithm 解釋如何找到所有排列，但我仍然試圖找到一種方法，只能得到顛倒後不一樣的排列。 – user802599 2012-02-13 04:21:01

如果您在這類事情上得到了強化，我建議您嘗試一下在項目euler上的一些問題，例如， http://projecteuler.net/problem=15

pythons itertools模塊它有一些示例代碼的例子。您可以將示例代碼轉換爲您選擇的編程語言。

http://docs.python.org/library/itertools.html

樣本功能：

product('ABCD', repeat=2)  AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD 
permutations('ABCD', 2)  AB AC AD BA BC BD CA CB CD DA DB DC 
combinations('ABCD', 2)  AB AC AD BC BD CD 
combinations_with_replacement('ABCD', 2)  AA AB AC AD BB BC BD CC CD DD

示例代碼：

def combinations(iterable, r): 
    # combinations('ABCD', 2) --> AB AC AD BC BD CD 
    # combinations(range(4), 3) --> 012 013 023 123 
    pool = tuple(iterable) 
    n = len(pool) 
    if r > n: 
     return 
    indices = range(r) 
    yield tuple(pool[i] for i in indices) 
    while True: 
     for i in reversed(range(r)): 
      if indices[i] != i + n - r: 
       break 
     else: 
      return 
     indices[i] += 1 
     for j in range(i+1, r): 
      indices[j] = indices[j-1] + 1 
     yield tuple(pool[i] for i in indices)

注意，在你上面的問題，如果你讓一個從點X1去，Y1點x2，y2在直線上的距離，那麼它不是同一個問題。（因爲您可以對點進行排序並將它們放入空間數據結構中）。我認爲在旅行推銷員問題中，你應該有「多風/多山的道路」，即使兩個點靠近x和y，他們也可能有一個大的加權邊緣連接它們。

來源

2012-01-10 04:34:23

我試着用這個編寫一些phython程序，但是這不會做我想做的事情。 – user802599 2012-02-13 04:25:40

啊運氣不好。保持練習。嘗試前幾個項目euler問題，然後查看論壇中的python解決方案，看看您的代碼如何比較。 – 2012-02-13 04:56:24

這裏是我的C＃類找到排列或組合：

public static class IEnumerableExtensions 
{ 
    public static IEnumerable<IEnumerable<T>> Arrange<T>(this IEnumerable<T> elements, 
     int places, bool allowRepeats = true, bool orderMatters = true) 
    { 
     return orderMatters ? 
      Permutate(elements, places, allowRepeats) : 
      Combine(elements, places, allowRepeats); 
    } 

    public static IEnumerable<IEnumerable<T>> Permutate<T>(this IEnumerable<T> elements, int places, bool allowRepeats = false) 
    { 
     foreach (var cur in elements) 
     { 
      if (places == 1) yield return cur.Yield(); 
      else 
      { 
       var sub = allowRepeats ? elements : elements.Where(v => !v.Equals(cur)); 
       foreach (var res in sub.Permutate(places - 1, allowRepeats)) 
       { 
        yield return res.Prepend(cur); 
       } 
      } 
     } 
    } 

    public static IEnumerable<IEnumerable<T>> Combine<T>(this IEnumerable<T> elements, int places, bool allowRepeats = false) 
    { 
     int i = 0; 
     foreach (var cur in elements) 
     { 
      if (places == 1) yield return cur.Yield(); 
      else 
      { 
       var sub = allowRepeats ? elements.Skip(i++) : elements.Skip(i++ + 1); 
       foreach (var res in sub.Combine(places - 1, allowRepeats)) 
       { 
        yield return res.Prepend(cur); 
       } 
      } 
     } 
    } 

    public static IEnumerable<T> Yield<T>(this T item) 
    { 
     yield return item; 
    } 

    static IEnumerable<T> Prepend<T>(this IEnumerable<T> rest, T first) 
    { 
     yield return first; 
     foreach (var item in rest) 
      yield return item; 
    } 
}

用法：

 var places = new char[] { 'A', 'B', 'C' }; 
     var routes = places.Permutate(3).ToArray(); 

     //to remove reverse routes: 
     var noRev = (from r1 in routes 
        from r2 in routes 
        where r1.SequenceEqual(r2.Reverse()) 
        select (r1.First() < r2.First() ? r1 : r2)).Distinct();

來源

2016-02-02 13:49:21 Tsayper

程序員的組合？

回答

相關問題