/* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { public static int numGroupingCombinations(int n, int groupSize) { if(n % groupSize != 0) return 0; // n must be a multiple of groupSize int count = 1; while(n > groupSize) { count *= nCr(n - 1, groupSize - 1); n -= groupSize; } return count; } public static int nCr(int n, int r) { int ret = 1; for (int k = 0; k < r; k++) { ret = ret * (n-k) / (k+1); } return ret; } public static void getKthCombination(int n, int r, int k, int[] c, int start, int offset) { if(r == 0) return; if(r == n) { for(int i = 0; i < r; i++) c[start + i] = i + offset; return; } int count = nCr(n - 1, r - 1); if(k < count) { c[start] = offset; getKthCombination(n-1, r-1, k, c, start + 1, offset + 1); return; } getKthCombination(n-1, r, k-count, c, start, offset + 1); } public static int[] getKthCombination(int n, int r, int k) { int[] c = new int[r]; getKthCombination(n, r, k, c, 0, 0); return c; } { if(elements.length % groupSize != 0) return; int remainingSize = elements.length - start; if(remainingSize == 0) { // output the elements: for(int i = 0; i < elements.length; i += groupSize) { for(int j = 0; j < groupSize; j++) } return; } int combinations = nCr(remainingSize - 1, groupSize - 1); // decide which combination of remaining elements to pair the first element with: int[] combination = getKthCombination(remainingSize - 1, groupSize - 1, index % combinations); // swap elements into place for(int i = 0; i < groupSize - 1; i++) { elements[start + 1 + i] = elements[start + 1 + combination[i]]; elements[start + 1 + combination[i]] = temp; } generateGrouping(elements, groupSize, start + groupSize, index / combinations); // swap them back: // for(int i = 0; i < groupSize - 1; i++) for(int i = groupSize - 2; i >= 0; i--) { elements[start + 1 + i] = elements[start + 1 + combination[i]]; elements[start + 1 + combination[i]] = temp; } } { int count = numGroupingCombinations(array.length, 2); for(int i = 0; i < count; i++) generateGrouping(array, 2, 0, i); count = numGroupingCombinations(array.length, 3); for(int i = 0; i < count; i++) generateGrouping(array, 3, 0, i); } }
Standard input is empty
nCr: 210 num pairings: 15 [A,B][C,D][E,F] [A,C][B,D][E,F] [A,D][C,B][E,F] [A,E][C,D][B,F] [A,F][C,D][E,B] [A,B][C,E][D,F] [A,C][B,E][D,F] [A,D][C,E][B,F] [A,E][C,B][D,F] [A,F][C,E][D,B] [A,B][C,F][E,D] [A,C][B,F][E,D] [A,D][C,F][E,B] [A,E][C,F][B,D] [A,F][C,B][E,D] num groups of 3: 10 [A,B,C][D,E,F] [A,B,D][C,E,F] [A,B,E][D,C,F] [A,B,F][D,E,C] [A,C,D][B,E,F] [A,C,E][D,B,F] [A,C,F][D,E,B] [A,D,E][B,C,F] [A,D,F][B,E,C] [A,E,F][D,B,C]