Enumerating Permutations of a set of subsets

Question

I have sets S1 = {s11,s12,s13), S2 = {s21,s22,s23) and so on till SN.I need to generate all the permutations consisting elements of S1,S2..SN.. such that there is only 1 element from each of the sets.

For eg:

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

My permuations would be:

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

How would I go about doing it? (I could randomly go about picking up 1 from each and merging them, but that is even in my knowledge a bad idea).

For the sake of generality assume that there are 'n' elements in each set. I am looking at implementing it in C. Please note that 'N' and 'n' is not fixed.

Answer 1

If you know exactly how many sets there are and it's a small number one might normally do this with nested loops. If the number of sets is greater than 2 or 3, or it is variable, then a recursive algorithm starts to make sense.

And if this is homework, it's likely that implementing a recursive algorithm is the object of the entire assignment. Think about it, for each set, you can call the enumeration function recursively and have it start enumerating the next set...

Answer 2

If they are in a container, just iterate through each:

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

Generic solution:

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 4

It's just a matter of recursion. Let's assume these definitions.

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.

The function is

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);
        }
    }
}

To generate the permutations, simply call permute(0);

Answer 5

This is a fairly simple iterative implementation which you should be able to adapt as necessary:

#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

The most efficient method I could come up with (in 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();
}