fork(1) download
copy 
  1. using System;
  2. using System.Numerics;
  3. using System.Collections.Generic;
  4.  
  5. public class Test
  6. {
  7.     // Helper functions for calculating values of (n choose k).
  8.     // These are not optimally coded!
  9. 	// ----------------------------------------------------------------------
  10. 	protected static BigInteger factorial(int n) {
  11. 		BigInteger f = 1;
  12. 		while (n > 1) f *= n--;
  13. 		return f;
  14. 	}
  15.  
  16. 	protected static int binomial(int n, int k) {
  17. 		if (k > n) return 0;
  18. 		return (int)(factorial(n) / (factorial(k) * factorial(n-k)));
  19. 	}
  20.  
  21. 	// In the combinatorial number system, a combination {c_1, c_2, ..., c_k}
  22. 	// corresponds to the integer value obtained by adding (c_1 choose 1) +
  23. 	// (c_2 choose 2) + ... + (c_k choose k)
  24. 	// NOTE: combination values are assumed to start from zero, so
  25. 	// a combination like {1, 2, 3, 4, 5} will give a non-zero result
  26. 	// ----------------------------------------------------------------------
  27. 	public static int combination_2_index(int[] combo) {
  28. 		int ix = 0, i = 1;
  29. 		Array.Sort(combo);
  30. 		foreach (int c in combo) {
  31. 			if (c > 0) ix += binomial(c, i);
  32. 			i++;
  33. 		}
  34. 		return ix;
  35. 	}
  36.  
  37. 	// The reverse of this process is a bit fiddly. See Wikipedia for an
  38. 	// explanation: https://e...content-available-to-author-only...a.org/wiki/Combinatorial_number_system
  39. 	// ----------------------------------------------------------------------
  40. 	public static int[] index_2_combination(int ix, int k) {
  41. 		List<int> combo_list = new List<int>();
  42. 		while (k >= 1) {
  43. 			int n = k - 1;
  44. 			if (ix == 0) {
  45. 				combo_list.Add(n);
  46. 				k--;
  47. 				continue;
  48. 			}
  49. 			int b = 0;
  50. 			while (true) {
  51. 			    // (Using a linear search here, but a binary search with
  52. 			    // precomputed binomial values would be faster)
  53. 				int b0 = b;
  54. 				b = binomial(n, k);
  55. 				if (b > ix || ix == 0) {
  56. 					ix -= b0;
  57. 					combo_list.Add(n-1);
  58. 					break;
  59. 				}
  60. 				n++;
  61. 			}
  62. 			k--;
  63. 		}
  64. 		int[] combo = combo_list.ToArray();
  65. 		Array.Sort(combo);
  66. 		return combo;
  67. 	}
  68.  
  69. 	public static void Main()
  70. 	{
  71. 		int[][] test_combos = new int[][] {
  72. 		    new int[] {0,1,2,3,4,5},
  73. 		    new int[] {0,1,2,3,4,6},
  74. 		    new int[] {38,40,41,42,43,44},
  75. 		    new int[] {39,40,41,42,43,44}
  76. 		};
  77. 		int ix;
  78. 		for (int i=0; i<test_combos.Length; i++) {
  79. 			ix = combination_2_index(test_combos[i]);
  80. 			int[] combo = index_2_combination(ix, test_combos[i].Length);
  81. 			Console.WriteLine("{0} -> [{1}]", ix, string.Join(", ", combo));
  82. 		}
  83. 	}
  84. }
  85.  
Success #stdin #stdout 0.03s 25184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 -> [0, 1, 2, 3, 4, 5]
1 -> [0, 1, 2, 3, 4, 6]
8145058 -> [38, 40, 41, 42, 43, 44]
8145059 -> [39, 40, 41, 42, 43, 44]
https://ideone.com/lxWvhu
language:
C# (gmcs 5.20.1)
created:
3 years ago
visibility:
secret

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!