Создание всех комбинаций пар без избыточности

Question

Мне нужно решить проблему для программного обеспечения чемпионата с открытым исходным кодом (в java). Это программное обеспечение может найти наилучшую комбинацию совпадений с различными критериями (рейтинг участников, уже выполненные матчи, ...).

В настоящее время используемый алгоритм не является оптимальным, поскольку он сравнивает все комбинации совпадений (включая избыточные комбинации). При таком подходе, sotfware сравнивает комбинации «факториал количества участников». Я ищу алгоритм, который генерирует все комбинации совпадений без избыточности.

Текущий код с примером с 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 

Как вы можете видеть, есть много избыточности ("А против В, С против D" это то же самое, что «B против A, C против D» и «B против A, D против 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 

Ваша помощь приветствуется.

Answer 1

Ответ на мой вопрос:

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

Найдено here.