fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.Collections;
  9. import java.util.HashMap;
  10. import java.util.Map;
  11. import java.util.Random;
  12.  
  13. /* Name of the class has to be "Main" only if the class is public. */
  14. class TuplesM
  15. {
  16.  
  17. 	final int k; // alphabet size
  18. 	final int n; // tple sise
  19. 	final int[] a; // available len: t 
  20. 	final Random rand = new Random();
  21.  
  22. 	Map<String, Integer> histo = new HashMap<>(); // for computing stats tests
  23.  
  24. 	public TuplesM(int[] ax, int n) {
  25. 		this.a = Arrays.copyOf(ax, ax.length);
  26. 		k = ax.length;
  27. 		this.n = n;
  28. 	}
  29.  
  30. 	public void addhistoTup(int[] tup) {
  31. 		StringBuilder sb = new StringBuilder();
  32. 		for( int t : tup )
  33. 			sb.append(t).append(":");
  34. 		String key = sb.toString();
  35. 		if( !histo.containsKey(key) ) histo.put(key, 1);
  36. 		else histo.put(key, histo.get(key) + 1);
  37. 	}
  38.  
  39. 	/* generates a random integer in 0... weight.length-1, according to the given weights */
  40. 	public int genRandom(int[] weight) {
  41. 		int ac = 0;
  42. 		for( int w : weight )
  43. 			ac += w;
  44. 		int r = rand.nextInt(ac);
  45. 		for( int i = 0, z = 0; i < weight.length; i++ ) {
  46. 			z += weight[i];
  47. 			if( r < z ) return i;
  48. 		}
  49. 		throw new RuntimeException("?");
  50. 	}
  51.  
  52. 	public int[] genTup() {
  53. 		int[] res = new int[n];
  54. 		int[] ac = Arrays.copyOf(a, a.length);
  55. 		int[] w = new int[k];
  56. 		for( int t = 0; t < n; t++ ) {
  57. 			for( int i = 0; i < k; i++ ) {
  58. 				ac[i] = ac[i] - 1;
  59. 				w[i] = ac[i] < 0 ? 0 : computeTups(ac, n - t - 1);
  60. 				ac[i] = ac[i] + 1;
  61. 			}
  62. 			int s = genRandom(w);
  63. 			res[t] = s;
  64. 			ac[s]--;
  65. 		}
  66. 		return res;
  67. 	}
  68.  
  69. 	void printHisto() {
  70. 		int s = histo.size();
  71. 		ArrayList<String> ks = new ArrayList<>(histo.keySet());
  72. 		Collections.sort(ks);
  73. 		for( String kss : ks ) {
  74. 			System.out.printf("%s : %.3f\n", kss, histo.get(kss) / (1.0 * s));
  75. 		}
  76. 	}
  77.  
  78. 	public static int computeTups(int[] avail, int n) {
  79. 		if( n == 0 ) return 1;
  80. 		int ac = 0;
  81. 		int[] availc = Arrays.copyOf(avail, avail.length);
  82. 		for( int i = 0; i < avail.length; i++ ) {
  83. 			if( availc[i] == 0 ) continue;
  84. 			availc[i]--;
  85. 			ac += computeTups(availc, n - 1);
  86. 			availc[i]++;
  87. 		}
  88. 		return ac;
  89. 	}
  90.  
  91. 	private static void test1(int [] a, int n) {
  92. 		TuplesM tm = new TuplesM(a,n);
  93. 		int tries = 100000;
  94. 		for( int k = 0; k < tries; k++ ) {
  95. 			int[] tup = tm.genTup();
  96. 			tm.addhistoTup(tup);
  97. 		}
  98. 		tm.printHisto();
  99. 	}
  100.  
  101.  
  102.  
  103. 	public static void main (String[] args) throws java.lang.Exception
  104. 	{
  105. 		int n = 2;
  106. 		int[] a=new int[] { 1, 2, 3 };
  107. 		test1(a,n);
  108. 	}
  109. }
Success #stdin #stdout 0.21s 321280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0:1: : 1552.375
0:2: : 1568.000
1:0: : 1562.875
1:1: : 1571.000
1:2: : 1562.125
2:0: : 1560.125
2:1: : 1569.250
2:2: : 1554.250
https://ideone.com/SfiWKu
language:
Java (HotSpot 12)
created:
10 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!