조합론?

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 

샘플 코드 : 당신의 위의 문제에서, 당신은 점 X1에서 이동을 허용하는 경우 있음

가

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) 

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