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

Question

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

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

поэтому, если у меня есть три точки A, B и CI, я бы хотел найти все различные комбинации A, B и C, где каждая используется только один раз, и набор не совпадает с другим набором, уже найденным, когда обратный.

например: азбука ACB BAC

Но как я могу вычислить все комбинации для любого количества точек?

Я писал эту программу для удовольствия, и теперь меня больше интересует поиск хорошего ресурса для изучения того, как решать комбинаторные задачи в программировании. Все, что я нашел для изучения комбинаторики, говорит мне, как найти количество возможных комбинаций, и бесполезно для фактического перечисления всех возможных комбинаций.

Answer 1

Если вас интересуют такие вещи, я рекомендую вам попробовать некоторые проблемы в проекте 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, они могут иметь большой взвешенный край, соединяющий их.

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();