fork(2) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static int numGroupingCombinations(int n, int groupSize)
  11. 	{
  12. 		if(n % groupSize != 0)
  13. 			return 0;	// n must be a multiple of groupSize
  14.  
  15. 		int count = 1;
  16. 		while(n > groupSize)
  17. 		{
  18. 			count *= nCr(n - 1, groupSize - 1);
  19. 			n -= groupSize;
  20. 		}
  21. 		return count;
  22. 	}
  23.  
  24. 	public static int nCr(int n, int r)
  25. 	{
  26. 		int ret = 1;
  27. 	    for (int k = 0; k < r; k++) {
  28. 	        ret = ret * (n-k) / (k+1);
  29. 	    }
  30. 	    return ret;	
  31. 	}
  32.  
  33. 	public static void getKthCombination(int n, int r, int k, int[] c, int start, int offset)
  34. 	{
  35. 		if(r == 0)
  36. 			return;
  37. 		if(r == n)
  38. 		{
  39. 			for(int i = 0; i < r; i++)
  40. 				c[start + i] = i + offset;
  41. 			return;
  42. 		}
  43. 		int count = nCr(n - 1, r - 1);
  44. 		if(k < count)
  45. 		{
  46. 			c[start] = offset;
  47. 		    getKthCombination(n-1, r-1, k, c, start + 1, offset + 1);
  48. 		    return;
  49. 		}
  50.         getKthCombination(n-1, r, k-count, c, start, offset + 1);
  51. 	}
  52.  
  53. 	public static int[] getKthCombination(int n, int r, int k)
  54. 	{
  55. 		int[] c = new int[r];
  56. 		getKthCombination(n, r, k, c, 0, 0);
  57.  
  58. 		return c;
  59. 	}
  60.  
  61. 	public static void generateGrouping(String[] elements, int groupSize, int start, int index)
  62. 	{
  63. 		if(elements.length % groupSize != 0)
  64. 			return;
  65.  
  66. 		int remainingSize = elements.length - start;
  67. 		if(remainingSize == 0)
  68. 		{
  69. 			// output the elements:
  70. 			for(int i = 0; i < elements.length; i += groupSize)
  71. 			{
  72. 				System.out.print("[");
  73. 				for(int j = 0; j < groupSize; j++)
  74. 					System.out.print(((j==0)?"":",")+elements[i+j]);
  75. 				System.out.print("]");
  76. 			}
  77. 			System.out.println("");
  78. 			return;	
  79. 		}
  80.  
  81. 		int combinations = nCr(remainingSize - 1, groupSize - 1);
  82.  
  83. 		// decide which combination of remaining elements to pair the first element with:
  84. 		int[] combination = getKthCombination(remainingSize - 1, groupSize - 1, index % combinations);
  85.  
  86. 		// swap elements into place
  87. 		for(int i = 0; i < groupSize - 1; i++)
  88. 		{
  89. 			String temp = elements[start + 1 + i];
  90. 			elements[start + 1 + i] = elements[start + 1 + combination[i]];
  91. 			elements[start + 1 + combination[i]] = temp;
  92. 		}
  93.  
  94. 		generateGrouping(elements, groupSize, start + groupSize, index / combinations);
  95.  
  96. 		// swap them back:
  97. 		// for(int i = 0; i < groupSize - 1; i++)
  98. 		for(int i = groupSize - 2; i >= 0; i--)
  99. 		{
  100. 			String temp = elements[start + 1 + i];
  101. 			elements[start + 1 + i] = elements[start + 1 + combination[i]];
  102. 			elements[start + 1 + combination[i]] = temp;
  103. 		}
  104. 	}
  105.  
  106. 	public static void main (String[] args) throws java.lang.Exception
  107. 	{
  108. 		String[] array = {"A", "B", "C", "D", "E", "F"};
  109.  
  110. 		System.out.println("nCr: " + nCr(10, 4));
  111.  
  112. 		int count = numGroupingCombinations(array.length, 2);
  113. 		System.out.println("num pairings: " + count);
  114.  
  115. 		for(int i = 0; i < count; i++)
  116. 			generateGrouping(array, 2, 0, i);
  117.  
  118. 		count = numGroupingCombinations(array.length, 3);
  119. 		System.out.println("num groups of 3: " + count);
  120.  
  121. 		for(int i = 0; i < count; i++)
  122. 			generateGrouping(array, 3, 0, i);
  123. 	}
  124. }
Success #stdin #stdout 0.05s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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]
https://ideone.com/1voqLQ
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!