-1

我必须解决一个开源锦标赛软件（在 java 中）的问题。该软件可以找到具有不同标准的比赛的最佳组合（参与者的排名，已经进行的比赛？，...）。

目前，使用的算法不是最优的，因为它比较匹配的所有组合（包括冗余组合）。使用这种方法，软件比较“参与者数量的阶乘”组合。我正在寻找一种生成所有匹配组合而没有冗余的算法。

当前代码带有 4 个参与者的示例：

// Example with 4 participants
public static void main (String[] args) {
   String[] participants = {"A","B","C","D"};
   double factorial = factorial(participants.length);
   for(double i=0;i<factorial;i++) {
      String[] combination = permutation(i,participants);
      System.out.println("Combination "+(int)i+" : "+combination[0]+" vs "+combination[1]+", "+combination[2]+" vs "+combination[3]);
   }
}

// Current code
public static <K> K[] permutation (double k, K[] objects) {
   K[] permutation = objects.clone();
   for (int i = 2; i < permutation.length + 1; i++) {
      k = k / (i - 1);
      swap(permutation, (int)(k % i), i - 1);
   }
   return permutation;
}
public static <K> void swap (K[] objects, int indexA, int indexB) {
   K temp = objects[indexA];
   objects[indexA] = objects[indexB];
   objects[indexB] = temp;
}
public static double factorial (int value) {
   double result = value;
   while (value != 2) {
      result *= --value;
   }
   return result;
}

输出 ：

Combination 0 : D vs A, B vs C
Combination 1 : D vs B, A vs C
Combination 2 : D vs C, A vs B
Combination 3 : D vs C, B vs A
Combination 4 : D vs A, C vs B
Combination 5 : D vs B, C vs A
Combination 6 : C vs D, B vs A
Combination 7 : C vs D, A vs B
Combination 8 : B vs D, A vs C
Combination 9 : A vs D, B vs C
Combination 10 : B vs D, C vs A
Combination 11 : A vs D, C vs B
Combination 12 : C vs A, D vs B
Combination 13 : C vs B, D vs A
Combination 14 : B vs C, D vs A
Combination 15 : A vs C, D vs B
Combination 16 : B vs A, D vs C
Combination 17 : A vs B, D vs C
Combination 18 : C vs A, B vs D
Combination 19 : C vs B, A vs D
Combination 20 : B vs C, A vs D
Combination 21 : A vs C, B vs D
Combination 22 : B vs A, C vs D
Combination 23 : A vs B, C vs D

如您所见，有很多冗余（“A vs B，C vs D”与“B vs A，C vs D”和“B vs A，D vs C”和...相同）。对于 10 名或更多参与者 (10! = 3.628.800...)，每个组合的比较损失时间（目的是找到最好的）是相当可观的。

所需输出的示例（无论顺序）：

Combination 0 : A vs B, C vs D
Combination 1 : A vs C, B vs D
Combination 2 : A vs D, B vs C

欢迎您的帮助。

4

1 回答 1

0

回答我的问题：

public void generate (int n) {
   int[] covered = new int[n];
   int[] list = new int[n];
   for (int i = 0; i < n; i++) {
      covered[i] = 0;
   }
   this.generate(n, covered, 0, list);
}
private void generate (int n, int[] covered, int i, int[] list) {
   int j = 0;
   while ((j < n) && (covered[j] == 1)) {
      j++;
   }
   if (j == n) {
      System.out.println(Arrays.toString(list));
      return;
   }
   covered[j] = 1;
   for (int k = 0; k < n; k++) {
      if (covered[k] == 0) {
         covered[k] = 1;
         list[i++] = j;
         list[i++] = k;
         this.generate(n, covered, i, list);
         i -= 2;
         covered[k] = 0;
      }
   }
   covered[j] = 0;
}

在这里找到。

于 2013-06-18T17:09:04.117 回答