1

S1 = {s11,s12,s13)、S2 = {s21,s22,s23) などのセットを 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」は固定されていないことに注意してください。

4

7 に答える 7

0

これはかなり単純な反復実装であり、必要に応じて適応できるはずです。

#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);
}
于 2009-10-11T09:10:58.267 に答える
0

セットの要素をサイクル カウンターの値と考えることができます。3 セットはサイクルの 3 を意味し (GMan アンサーのように)、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 );
}
于 2009-10-11T11:54:38.567 に答える
0

セットの数が正確にわかっていて、その数が少ない場合は、通常、ネストされたループでこれを行うことができます。セットの数が 2 または 3 より大きい場合、または可変の場合は、再帰アルゴリズムが意味を成し始めます。

これが宿題である場合、再帰アルゴリズムの実装が課題全体の目的である可能性があります。考えてみてください。セットごとに、列挙関数を再帰的に呼び出して、次のセットの列挙を開始させることができます...

于 2009-10-11T08:11:17.187 に答える
0

それらがコンテナー内にある場合は、それぞれを反復処理します。

#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;
}
于 2009-10-11T08:12:49.740 に答える
0

私が思いついた最も効率的な方法（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();
}
于 2010-04-23T17:55:23.960 に答える
0

一般的な解決策:

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

}
于 2009-10-11T08:16:24.803 に答える
0

それは単なる再帰の問題です。これらの定義を仮定しましょう。

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

于 2009-10-11T08:56:28.950 に答える