程序员的组合数学？

Question

我开始编写一个 C# Silverlight 程序，尝试找到解决旅行推销员问题的强力解决方案。但一直在尝试找出所有可能的路线。

对于我的程序，我生成随机点并尝试找到可以将它们全部连接起来的最短线，而无需访问任何两次。

所以如果我有三个点 A,B, & CI 想要找到 A、B 和 A 的所有不同组合。 C，其中每个仅使用一次，并且该集合与颠倒时已找到的另一个集合不同。

例如： ABC ACB BAC

但是我怎样才能计算任意数量的点的所有组合呢？

我编写这个程序是为了好玩，现在我更感兴趣的是找到一个好的资源来学习如何解决编程中的组合问题。我为学习组合学找到的所有内容都告诉我如何找到可能的组合数量，但对于实际枚举所有可能的组合毫无用处。

Answer 1

如果您对此类事情感兴趣，我建议您尝试一下 euler 项目上的一些问题，例如 http ://projecteuler.net/problem=15

在 python 的 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();

Answer 3

这里有一个Python的解决方案。第一个函数是一个递归函数，它生成与输入列表长度 n 相同的所有排列 P(n,n)。第二个函数运行第一个函数并过滤掉任何已存在反向排列的排列。

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']]