combinatorics for programmers?

Question

I started writing a C# Silverlight program to try and find brute force solutions to the travelling sales man problems. But got stuck on trying to figure out all the possible routes.

For my program I am generating random dots and trying to find the shortest line that can join them all, without visiting any twice.

so if I have three dots A,B, & C I would want to find all the different combinations of A,B, & C, where each is only used once and the set is not the same as another set already found when reversed.

eg: ABC ACB BAC

But how can I compute all the combinations for any number of dots?

I was writing this program for fun and I am now more interested in finding a good resource for learning about how to solve combinatorial problems in programming. Everything I have found for learning combinatorics tells me how to find to number of possible combinations and is useless for actually enumerating all the possible combinations.

Answer 1

Here is a solution in Python. The first function is a recursive function that generates all permutations P(n,n) of the same length n as the input list. The second function runs the first one and filters out any permutation whose reverse already exists.

def all_perms(elements):
    """
    Recursive function to generate all permutations
    :param elements: a list
    """
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

def filtered_perms(elements):
    """
    Filters out any permutation whose reverse already exists
    :param elements: a list
    """
    result = []
    for perm in all_perms(elements):
        if list(reversed(perm)) not in result:
            result.append(perm)
    print(result)

filtered_perms(["A", "B", "C"])
#[['A', 'B', 'C'], ['B', 'A', 'C'], ['B', 'C', 'A']]

Answer 2

Here's my C# class to find permutations or combinations:

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

Usage:

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

Answer 3

If you're getting intertested in this sort of thing, i recommend you try out some of the problems on project euler, e.g. http://projecteuler.net/problem=15

In pythons itertools module it has some examples with example code. You could convert the sample code to the programming language of your choice.

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

sample functions:

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

sample code:

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)

Note that in your above problem, if you are allowing one to go from point x1,y1 to point x2,y2 in straight line distance, then it isn't the same problem. (as you can sort the points and put them into a spatial datastructure). I Think in the traveling salesman problem, you're supposed to have "windy/hilly roads" so that even if two points are close together in terms of x and y, they may have a large weighted edge connecting them.