程序员的组合数学？

Question

我开始编写一款C# Silverlight程序，尝试用暴力方法解决旅行商问题。但我卡在了如何找出所有可能的路线上。

对于我的程序，我正在生成随机点，并试图找到可以连接它们所有的最短线路，而不重复访问任何一个点。

所以，如果我有三个点A、B、C，我想要找到所有不同的A、B、C组合，其中每个点只使用一次，且该组合与已经找到的反向组合不同。

例如： ABC ACB BAC

但是，如何计算任意数量点的所有组合？

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

- user802599

---

顺便说一下，那也是一个排列。谷歌搜索“获取列表的所有排列”，您会找到很多结果。 - Ry-

我仍然没有找到答案，我已经搜索了互联网、我的大学图书馆并与我的大学数学教授交谈。我确实找到了这个链接 http://bytes.com/topic/c/answers/536779-richard-heathfields-tsp-permutation-algorithm其中解释了如何找到所有排列，但我仍在尝试找到一种方法，只获取不同于反转时的排列。 - user802599

Answer 1

这是我的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();

- Mike Tsayper

Answer 2

如果你对这种事情感兴趣，我建议你尝试一下project 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方面非常接近，它们之间可能会有一个大的加权边连接。

- Rusty Rob

---

我尝试使用此编程语言编写了几个Python程序，但它并没有实现我想要的功能。 - user802599

啊，真不幸。继续练习吧。尝试解决前几个项目欧拉问题，并在论坛中查看Python解决方案，以比较您的代码。 - Rusty Rob

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

- pakpe