プログラマのためのコンビナトリアル？

Question

私は、C＃Silverlightプログラムを書いて、旅行中のセールスマンの問題に対する強力な解決策を見つけようとしました。しかし、すべての可能なルートを把握しようとしていました。

私のプログラムでは、ランダムなドットを生成しています。それらのドットを2度訪れることなく、すべて参加できる最短の行を見つけようとしています。

ので、私は3つのドットA、Bを持っている場合は、& CIは、それぞれが一度だけ使用されるA、B、& C、すべての異なる組み合わせを見つけるしたいとのセットがすでに見つかっ別のセットと同じではありません逆転したとき。

例： ABC ACB BAC

しかし、どのように私は、ドットの任意の数のすべての組み合わせを計算することができますか？

私は楽しみのためにこのプログラムを書いていたし、私は今、プログラミングで組合せ問題を解決する方法について学習するための優れたリソースを見つけることで、より興味を持っています。私がコンビナトリアルを学ぶために見つけたことは、可能な組み合わせの数を見つける方法を教えてくれるし、すべての可能な組み合わせを実際に列挙するのに役に立たない。

Answer 1

このようなことで相互参照が行われている場合は、プロジェクトオイラーの問題のいくつかを試してみることをおすすめします。 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) 

（注）1ポイントにポイントX1、Y1から行くことを許可しているあなたの上記の問題で、場合ということx2、y2を直線距離に置くと、同じ問題ではありません。 （ポイントをソートして空間データ構造に入れることができます）。私はあなたが2つの点がxとyの面で接近している場合でも、彼らはそれらを接続する大規模な重み付きエッジを持つことができるように、「風/丘陵道路を」持っていることになっている、巡回セールスマン問題で考えてみてください。

Answer 2

はここ順列や組み合わせを見つけるために、私の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();