Поиск всех возможных комбинаций без дублирования выбора?

Question

Как бы вы пишете что-то, что выбирает все возможные комбинации троек из массива {1, 2, 3, ..., N-1, N} без дубликатов? Это из недавнего конкурса программирования. N кратно 3.

примера, используя массив {1,2,3,4,5,6}:

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)

Это должно дать вам ваш результат без особых причудливых работ.

EDIT: Я ждал, когда кто-то обнаружит проблему с вышеуказанным, и это было действительно замечено. Способ исправления повторений состоит в следующем:

Шаг 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!)/(^ (N/3)) * ((N/3)!) ((3!)) Позиция (prove). вы можете просто использовать рекурсивный алгоритм для предоставления всех возможных комбинаций троек из массива {1, 2, 3, ..., N-1, N} без дубликатов. , но для производства одного из них вы можете использовать любую идею, такую ​​как user1952500 идея (хотя этот алгоритм также генерирует (N/3)! Дубликат позиции) или каждый, например, вы неизменяете last- (N-6) -member и ставите свой раствор для первого 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. первого определите T = floor (N/3) как количество триплетов в каждом наборе, поддерживаемых N элементами. Затем обратите внимание, что поскольку дублирующие триплеты нежелательны, триплеты в каждом наборе триплетов могут быть отсортированы по возрастанию по первому элементу без потери общности. Тогда общее количество триплетных множеств для N равно:

товар как t: 0 -> T-1 of ((N - 3 * t - 1) * (N - 3 * t - 2)/2)

Из этой формулы прямо видно, как построить алгоритм (грубой силы) для генерации триплетов.

Обновление: Вышеуказанное работает только для N% 3 == 0. Сейчас я работаю над обобщением. Forced; см комментарий по 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) = 28 * 10 = 280

Как вы в я предполагаю, что вам не нужен какой-либо код.

Обновление # 2: Обратите внимание, что для автоматического устранения дубликатов, первый элемент каждого триплета должен быть вынужден с наименьшим номером невыбранного элемента.