Перечисления Перестановки набора подмножеств

Question

У меня есть множества S1 = {s11, s12, s13), S2 = {s21, s22, s23) и т. Д. До SN.I нужно сгенерировать все перестановки, состоящие из элементов S1, S2..SN .., так что есть только 1 элемент из каждого набора.

Для например:

S1 = {a,b,c} 
S2 = {d,e,f} 
S3 = {g,h,i} 

Мой permuations будет:

{a,d,g}, {a,d,h}, {a,d,i}, {a,e,g}, {a,e,h}.... 

Как бы я идти о делать это? (Я мог бы случайным образом собирать 1 из каждого и объединять их, но это даже, насколько мне известно, плохая идея).

Для общности предположим, что в каждом наборе есть «n» элементов. Я смотрю на его реализацию в C. Обратите внимание, что 'N' и 'n' не фиксированы.

Answer 1

Это всего лишь вопрос рекурсии. Предположим, что эти определения.

const int MAXE = 1000, MAXN = 1000; 
int N;    // number of sets. 
int num[MAXN];  // number of elements of each set. 
int set[MAXN][MAXE]; // elements of each set. i-th set has elements from 
         // set[i][0] until set[i][num[i]-1]. 
int result[MAXN];  // temporary array to hold each permutation. 

Функция

void permute(int i) 
{ 
    if (i == N) 
    { 
     for (int j = 0; j < N; j++) 
      printf("%d%c", result[j], j==N-1 ? '\n' : ' '); 
    } 
    else 
    { 
     for (int j = 0; j < num[i]; j++) 
     { 
      result[i] = set[i][j]; 
      permute(i+1); 
     } 
    } 
} 

Для генерации перестановок, просто вызовите permute(0);

Answer 2

Если вы точно знаете, сколько наборов существует, и это небольшое число, обычно это можно сделать с вложенными циклами. Если число наборов больше 2 или 3, или оно является переменным, то рекурсивный алгоритм начинает иметь смысл.

И если это домашняя работа, вполне вероятно, что реализация рекурсивного алгоритма является объектом всего присваивания. Подумайте об этом, для каждого набора, вы можете вызвать функцию перечисления рекурсивно и он начать перечислять следующий набор ...

Answer 3

Если они находятся в контейнере, просто перебирать каждый:

#include <stdio.h> 

int main(void) 
{ 
    int set1[] = {1, 2, 3}; 
    int set2[] = {4, 5, 6}; 
    int set3[] = {7, 8, 9}; 

    for (unsigned i = 0; i < 3; ++i) 
    { 
     for (unsigned j = 0; j < 3; ++j) 
     { 
      for (unsigned k = 0; k < 3; ++k) 
      { 
       printf("(%d, %d, %d)", set1[i], set2[j], set3[k]); 
      } 
     } 
    } 

    return 0; 
} 

Answer 4

Generic раствор:

typedef struct sett 
{ 
    int* nums; 
    int size; 
} t_set; 


inline void swap(t_set *set, int a, int b) 
{ 
    int tmp = set->nums[a]; 
    set->nums[a] = set->nums[b]; 
    set->nums[b] = tmp; 
} 

void permute_set(t_set *set, int from, void func(t_set *)) 
{ 
    int i; 
    if (from == set->size - 1) { 
    func(set); 
    return; 
    } 
    for (i = from; i < set->size; i++) { 
    swap(set, from, i); 
    permute_set(set, from + 1, func); 
    swap(set, i, from); 
    } 
} 


t_set* create_set(int size) 
{ 
    t_set *set = (t_set*) calloc(1, sizeof(t_set)); 
    int i; 
    set->size = size; 
    set->nums = (int*) calloc(set->size, sizeof(int)); 
    for(i = 0; i < set->size; i++) 
    set->nums[i] = i + 1; 
    return set; 
} 

void print_set(t_set *set) { 
    int i; 
    if (set) { 
    for (i = 0; i < set->size; i++) 
     printf("%d ", set->nums[i]); 
    printf("\n"); 
    } 
} 

int main(int argc, char **argv) 
{ 
    t_set *set = create_set(4); 
    permute_set(set, 0, print_set); 

} 

Answer 5

Это довольно простой итеративный реализации, которые вы должны быть в состоянии адаптироваться по мере необходимости:

#define SETSIZE 3 
#define NSETS 4 

void permute(void) 
{ 
    char setofsets[NSETS][SETSIZE] = { 
     { 'a', 'b', 'c'}, 
     { 'd', 'e', 'f'}, 
     { 'g', 'h', 'i'}, 
     { 'j', 'k', 'l'}}; 
    char result[NSETS + 1]; 
    int i[NSETS]; /* loop indexes, one for each set */ 
    int j; 

    /* intialise loop indexes */ 
    for (j = 0; j < NSETS; j++) 
     i[j] = 0; 

    do { 
     /* Construct permutation as string */ 
     for (j = 0; j < NSETS; j++) 
      result[j] = setofsets[j][i[j]]; 
     result[NSETS] = '\0'; 

     printf("%s\n", result); 

     /* Increment indexes, starting from last set */ 
     j = NSETS; 
     do { 
      j--; 
      i[j] = (i[j] + 1) % SETSIZE; 

     } while (i[j] == 0 && j > 0); 
    } while (j > 0 || i[j] != 0); 
} 

Answer 6

Вы можете думать о элементах набора как значениях счетчик циклов. 3 комплекта означает 3 для циклов (как в GMan answare), N-наборы означает N (эмулировать) циклы:

#include <stdlib.h> 
#include <stdio.h> 

int set[3][2] = { {1,2}, {3,4}, {5,6} }; 

void print_set(int *ndx, int num_rows){ 
    for(int i=0; i<num_rows; i++) printf("%i ", set[i][ndx[i]]); 
    puts(""); 
} 

int main(){ 
    int num_cols = sizeof(set[0])/sizeof(set[0][0]); 
    int num_rows = sizeof(set)/sizeof(set[0]); 
    int *ndx = malloc(num_rows * sizeof(*ndx)); 

    int i=0; ndx[i] = -1; 
    do{ 
    ndx[i]++; while(++i<num_rows) ndx[i]=0; 
    print_set(ndx, num_rows); 
    while(--i>=0 && ndx[i]>=num_cols-1); 
    }while(i>=0); 
} 

Answer 7

Наиболее эффективный метод, который я мог придумать (в C#):

string[] sets = new string[] { "abc", "def", "gh" }; 
int count = 1; 
foreach (string set in sets) 
{ 
    count *= set.Length; 
} 

for (int i = 0; i < count; ++i) 
{ 
    var prev = count; 
    foreach (string set in sets) 
    { 
     prev = prev/set.Length; 
     Console.Write(set[(i/prev) % set.Length]); 
     Console.Write(" "); 
    } 

    Console.WriteLine(); 
}