Комбинаторика для программистов?

Question

Я начал писать программу C# Silverlight, чтобы попытаться найти решения грубой силы для проблем мужчин с распродажами. Но застрял, пытаясь выяснить все возможные маршруты.

Для моей программы я генерирую случайные точки и пытаясь найти кратчайшую строку, которая может присоединиться к ним, без посещения каких-либо дважды.

так что если у меня есть три точки 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) 

Обратите внимание, что в вашей выше проблемы, если вы разрешаете один идти из точки x1, y1, чтобы указать x2, y2 в прямом расстоянии, то это не та же проблема. (так как вы можете сортировать точки и помещать их в пространственную структуру данных). Я думаю, что в проблеме коммивояжера вы должны иметь «ветреные/холмистые дороги», так что даже если две точки близки друг к другу в терминах 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();