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

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}

Мои перестановки были бы:

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

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

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

Answer 1

Вы можете думать об элементах набора как о значениях счетчика цикла. 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 2

Самый эффективный метод, который я мог придумать (в 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();
}

Answer 3

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

#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 4

Это просто вопрос рекурсии. Давайте предположим, что эти определения.

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 5

Универсальное решение:

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 6

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

#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 7

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

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