4

重複なしで配列 {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} }

ではありません。

4

4 に答える 4

2

N は 3 の倍数なので、次のトリックを使用して解くことができます。

  1. 数値のすべての順列を昇順に生成します
  2. 順列ごとに、数値を直接 3 つのセット (0-2、3-6、...、N-2..N) に分割します。

これにより、派手な作業をしなくても結果が得られるはずです。

編集：誰かが上記の問題を発見するのを待っていましたが、実際に発見されました。繰り返しを修正する方法は、追加の手順を実行することです。

ステップ 3: いずれかのトリプルが辞書編集的にソートされていない形式である場合、そのセットを破棄します。それ以外の場合は続行します。

于 2013-03-15T07:29:49.207 に答える
2

あなたは (N!) / ( ((3!)^(N/3)) * ((N/3)!)) 位置 (証明) を持っています。再帰アルゴリズムを使用して、配列 {1, 2, 3, ..., N-1, N} からのトリプルのすべての可能な組み合わせを重複なしで提供できます。しかし、それらの1つを生成するには、user1952500アイデア（ただし、このアルゴリズムは（N / 3）！位置の重複も生成します）またはすべて、たとえば不変の最後の（N-6）メンバーを使用して、ソリューションを配置します結果の最初の最初の 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;
    }
于 2013-03-15T12:18:34.867 に答える
1 
#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");
}
于 2013-03-15T07:49:13.527 に答える
0

このような別個のトリプレット セットが N に対していくつ存在するかを考えてみましょう。まず、T = floor(N/3) を、N 個の要素によってサポートされる各セット内のトリプレットの数として定義します。次に、トリプレットの重複は望ましくないため、各トリプレット セットのトリプレットは、一般性を失うことなく、最初の要素で昇順に並べ替えることができます。次に、N のトリプレット セットの総数は次のとおりです。

t としての積: 0 -> T-1 of ( (N - 3*t - 1) * (N - 3*t - 2) / 2 )

この式から、トリプレットを生成する (力ずくの) アルゴリズムを構築する方法は簡単にわかります。

更新:上記は N % 3 == 0 でのみ機能します。現在、一般化に取り組んでいます。強制; 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: 重複を自動的に排除するには、各トリプレットの最初の要素を最小番号の選択されていない要素に強制する必要があることに注意してください。

于 2013-03-15T13:20:00.473 に答える