[algorithm] n에서 k 요소의 모든 조합을 반환하는 알고리즘

컴퓨터 프로그래밍 기술 4 권 : Fascicle 3 에는 내가 설명하는 것보다 특정 상황에 더 잘 맞는 톤이 많이 있습니다.

회색 코드

당신이 겪게 될 문제는 물론 메모리이며 꽤 빨리, 당신은 ²⁰ C ₃ = 1140 의 세트에 20 개의 요소에 의해 문제를 겪을 것입니다. 그리고 세트를 반복하고 싶다면 수정 된 회색을 사용하는 것이 가장 좋습니다 코드 알고리즘을 사용하므로 메모리에 모두 포함되어 있지 않습니다. 이것들은 이전의 다음 조합을 생성하고 반복을 피합니다. 다양한 용도로 사용할 수있는 것들이 많이 있습니다. 연속 조합의 차이를 극대화하고 싶습니까? 최소화? 등등.

회색 코드를 설명하는 원본 논문 중 일부 :

1. 일부 해밀턴 경로 및 최소 변경 알고리즘
2. 인접 교환 조합 생성 알고리즘

이 주제를 다루는 다른 논문들도 있습니다 :

1. Eades, Hickey, Adjacent Interchange Combination Generation 알고리즘의 효율적인 구현 (PDF, Pascal의 코드)
2. 조합 생성기
3. 조합 회색 코드 조사 (PostScript)
4. 그레이 코드 알고리즘

체이스 트위들 (알고리즘)

Phillip J Chase,` Algorithm 382 : N Objects에서 M의 조합 ‘(1970)

C의 알고리즘 …

사전 순서의 조합 색인 (버클 알고리즘 515)

색인으로 사전 조합을 참조 할 수도 있습니다. 인덱스가 인덱스를 기준으로 오른쪽에서 왼쪽으로 어느 정도 변경되어야한다는 것을 인식하고 조합을 복구해야하는 것을 구성 할 수 있습니다.

따라서 {1,2,3,4,5,6} 세트가 있으며 세 가지 요소가 필요합니다. {1,2,3}이라고 말하면 요소들 사이의 차이는 하나이며 순서는 최소입니다. {1,2,4}는 하나의 변경 사항이 있고 사전 식적으로 번호 2입니다. 따라서 마지막 위치의 ‘변경 사항’수는 사전 순서에서 하나의 변경을 설명합니다. 한 번의 변경 {1,3,4}가있는 두 번째 장소는 한 번의 변경이 있지만 두 번째 장소 (원래 세트의 요소 수에 비례)이기 때문에 더 많은 변화를 설명합니다.

내가 설명한 방법은 설정에서 색인에 이르기까지 해체로, 그 반대를 수행해야합니다. 이는 훨씬 까다로운 작업입니다. 이것이 버클 이 문제를 해결하는 방법입니다. 나는 약간의 변경 사항 으로 계산하기 위해 약간의 C를 작성했습니다. 나는 세트를 나타 내기 위해 숫자 범위가 아닌 세트의 인덱스를 사용했기 때문에 항상 0에서 n까지 작업하고 있습니다. 노트 :

1. 조합은 순서가 정해지지 않기 때문에 {1,3,2} = {1,2,3}-사전 식 순서로 정렬합니다.
2. 이 방법에는 첫 번째 차이에 대한 세트를 시작하는 암시 적 0이 있습니다.

사전 순서 (McCaffrey)의 조합 색인

이 다른 방법 의 개념 이해 및 프로그램에보다 쉽게이지만, 버클의 최적화를하지 않고 다음과 같습니다. 다행히도 중복 조합을 생성하지 않습니다.

세트 극대화 곳 .

예를 들면 다음과 같습니다 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1).. 따라서 네 가지를 포함하는 27 번째 사전 사전 조합은 다음과 같습니다. {1,2,5,6}, 이것들은 당신이보고 싶은 모든 세트의 인덱스입니다. 아래 예 (OCaml)에는 choose기능이 필요 하며 리더에게 맡겨야합니다.

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

작고 간단한 조합 반복자

교훈적인 목적으로 다음 두 알고리즘이 제공됩니다. 그들은 반복자와 (보다 일반적인) 폴더 전체 조합을 구현합니다. 그것들은 복잡성 O ( ⁿ C _k )를 갖는 가능한 한 빠르다 . 메모리 소비는에 의해 제한됩니다 k.

반복자부터 시작하여 각 조합에 대해 사용자가 제공 한 함수를 호출합니다.

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

보다 일반적인 버전은 초기 상태에서 시작하여 상태 변수와 함께 사용자 제공 함수를 호출합니다. 서로 다른 상태 사이에서 상태를 전달해야하므로 for 루프를 사용하지 않고 재귀를 사용합니다.

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

답변

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

123
124
125
134
135
145
234
235
245
345

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }
}

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

>>> len(list(choose_iter("abcdefgh",3)))
56

ABCDEFGH
^ ^ ^
아이크

ABCDEFGH
^ ^ ^
아이크

ABCDEFGH
^ ^ ^
아이크

ABCDEFGH
^ ^ ^
아이크

ABCDEFGH
  ^ ^ ^
  아이크

ABCDEFGH
  ^ ^ ^
  아이크
...

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

123
124
125
134
135
145
234
235
245
345