선택을 복제하지 않고 가능한 모든 조합 찾기?

Question

배열 {1, 2, 3, ..., N-1, N}에서 가능한 모든 트리플 조합을 중복없이 선택하는 방법은 무엇입니까? 이것은 최근 개최 된 프로그래밍 경쟁에서 나온 것입니다. N은 어레이 {1,2,3,4,5,6}를 사용 3.

예의 배수 :

C_1 = { {1,2,3}, {4,5,6} } 
C_2 = { {1,2,4}, {3,5,6} } 
C_3 = { {1,2,5}, {3,4,6} } 

모든 유효하지만

C_bad1 = { {1,2,3}, {3, 4, 5} } 
C_bad2 = { {1,2,4}, {3, 5, 6}, {1, 2, 5} } 

는 없다.

Answer 1

N이 3의 배수 우리 트릭 사용하여 해결할 수 있으므로 : 집합으로 숫자

1. 각 순열 모든 순열을 오름차순
2. 의 숫자 생성, 파티션 3 직접 (0-2, 3-6, ..., N-2..N)

그다지 멋진 결과없이 결과를 얻을 수 있습니다.

편집 : 나는 누군가가 위의 문제를 발견하기를 기다리고 있었고 실제로 발견되었습니다. 반복을 수정하는 방법은 추가 단계가 있어야합니다.

3 단계 : 사전이 사전 순으로 정렬되지 않은 경우 양식을 삭제합니다. 그렇지 않으면 계속하십시오.

Answer 2

#include <stdio.h> 

#define SEL_NUM 3 
#define LIST_SIZE 6 

void printset(int *list, int *map, int size); 
void select(int *list, int *map, int n, int size, int start); 

int main(int argc, const char **argv) { 
    int list[LIST_SIZE] = {1, 2, 3, 4, 5, 6}; 
    int map[LIST_SIZE] = {0}; 

    select(list, map, SEL_NUM, LIST_SIZE, 0); 

    return 0; 
} 

void select(int *list, int *map, int n, int size, int start) { 
    if (n == 0) { 
    printset(list, map, size); 
    return; 
    } 
    for (int i = start; i < size; i++) { 
    map[i] = 1; 
    select(list, map, n - 1, size, i + 1); 
    map[i] = 0; 
    } 
} 

void printset(int *list, int *map, int size) { 
    int list1[SEL_NUM], list2[SEL_NUM], list1cnt = 0, list2cnt = 0; 
    for (int i = 0; i < size; i++) 
    if (map[i]) 
     list1[list1cnt++] = list[i]; 
    else 
     list2[list2cnt++] = list[i]; 
    for (int i = 0; i < list1cnt; i++) 
    printf(" %d ", list1[i]); 
    printf(" -- "); 
    for (int i = 0; i < list2cnt; i++) 
    printf(" %d ", list2[i]); 
    printf("\n"); 
} 

Answer 3

당신은 (N!)/(((3,2)^(N/3)) * ((N/3)!))의 위치 (prove). 당신은 배열 {1, 2, 3, ..., N-1, N}에서 가능한 모든 트리플 조합을 중복없이 제공하기 위해 재귀 알고리즘을 사용할 수 있습니다. 하지만 그 중 하나를 생산하기 위해서는 user1952500 아이디어와 같은 아이디어를 사용할 수 있습니다 (이 알고리즘은 (N/3)! 위치 중복을 생성하지만) 또는 모든 예를 들어, 불변의 마지막 (N- 6) 당신의 결과의 시작의 첫 6 명에 대한 솔루션 (이 알고리즘은 중복 된 위치를 생성하지 않습니다)

재귀 솔루션 :.

void combtriples(int begin) 
    { 
    for(int i=1;i<=(n/3);i++) 
     for(int j=1;j<=(n/3);j++) 
     for(int k=1;k<=(n/3);k++) 
     { 
     if ((mark[i]<3) && (mark[j]<3) && (mark[k]<3)) 
      { 
      count-position++; 
      c[count][3]=begin; 
      c[count][4]=begin+1; 
      c[count][5]=begin+2; 
      mark[i]++; 
      mark[j]++; 
      mark[k]++; 
      count-member-flase=count-member-flase+3; 
      if (count-member-flase > 0) 
      { 
      combtriples(begin+3); 
      } 
      } 
     } 
    } 


    int main() 
    { 
    int mark[]; 
    int c[][]; 
    count-position=0; 
    count-member-flase=0; 
    combtriples(1); 
    return 0; 
    } 

Answer 4

이의는 별개의 삼중-세트 N. 먼저 존재 얼마나 많은 생각 해보자 N 개의 요소가 지원하는 각 집합의 삼중 항의 수를 T = floor (N/3)로 정의하십시오. 그런 다음 중복 된 3 중음을 원하지 않으므로 각 3 중첩 세트의 3 중음을 일반성의 손실없이 첫 번째 요소에 따라 오름차순으로 정렬 할 수 있습니다. 그러면 N에 대한 총 셋트 수는 다음과 같습니다.

곱 : (N - 3 * t - 1) * (N - 3 * t - 2)/2의 t : 0 -

이 수식에서 삼중 항을 생성하는 (무차별 대입) 알고리즘을 작성하는 방법은 간단합니다.

업데이트 : 위의 내용은 N % 3 == 0에서만 작동합니다. 이제 일반화 작업을하고 있습니다. 강제; OP로 주석을 볼

케이스 :

1. N < 3 수율 0
2. N = 3 개 수율 1
3. N = 6 개 수율 (5 * 4/2) * (2 * 1/2) = 10
4. N = 9 개 수율 (8 * 7/2) * (5 * 4/2) * (2 * 1/2) = * 10 = 280

28는 (A)에있는 바와 같이 프로그래밍 경쟁, 나는 당신이 어떤 코드도 필요 없다고 생각한다.

업데이트 # 2 : 자동으로 중복을 제거하는 참고, 각 삼중의 첫 번째 요소는 가장 낮은 번호의 선택되지 않은 요소에 강제해야합니다.