fork download
copy 
  1. import std.algorithm;
  2. import std.array;
  3. import std.format;
  4. import std.random;
  5. import std.range;
  6. import std.stdio;
  7. import std.typecons;
  8.  
  9. immutable int steps = 1_000_000;
  10.  
  11. int [] randomPermutation (int n)
  12. {
  13. 	int [] res;
  14. 	res.reserve (n);
  15.  
  16. 	alias Interval = Tuple !(int, q{lo}, int, q{hi});
  17. 	Interval [] c;
  18. 	c ~= Interval (0, n);
  19. 	while (!c.empty)
  20. 	{
  21. 		auto p = uniform (0, c.length);
  22. 		auto i = c[p];
  23. 		c[p] = c[$ - 1];
  24. 		c.length -= 1;
  25. 		c.assumeSafeAppend ();
  26. 		auto me = uniform (i.lo, i.hi);
  27. 		res ~= me;
  28. 		if (i.lo < me)
  29. 		{
  30. 			c ~= Interval (i.lo, me);
  31. 		}
  32. 		me += 1;
  33. 		if (me < i.hi)
  34. 		{
  35. 			c ~= Interval (me, i.hi);
  36. 		}
  37. 	}
  38.  
  39. 	return res;
  40. }
  41.  
  42. void main ()
  43. {
  44. 	int [int []] s;
  45. 	int n = 5;
  46. 	rndGen.seed (123);
  47. 	foreach (step; 0..steps)
  48. 	{
  49. 		auto q = randomPermutation (n);
  50. 		s[q.idup] += 1;
  51. 	}
  52. 	string [] t;
  53. 	foreach (p; s.byKeyValue ())
  54. 	{
  55. 		t ~= format ("%s: %s", p.key, p.value);
  56. 	}
  57. 	sort (t);
  58. 	writefln ("%-(%s\n%)", t);
  59. }
  60.  
Success #stdin #stdout 1.46s 16576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0, 1, 2, 3, 4]: 8452
[0, 1, 2, 4, 3]: 8501
[0, 1, 3, 2, 4]: 8388
[0, 1, 3, 4, 2]: 8336
[0, 1, 4, 2, 3]: 8125
[0, 1, 4, 3, 2]: 8410
[0, 2, 1, 3, 4]: 12362
[0, 2, 1, 4, 3]: 12514
[0, 2, 3, 1, 4]: 6204
[0, 2, 3, 4, 1]: 6293
[0, 2, 4, 1, 3]: 6346
[0, 2, 4, 3, 1]: 6254
[0, 3, 1, 2, 4]: 6034
[0, 3, 1, 4, 2]: 6387
[0, 3, 2, 1, 4]: 6228
[0, 3, 2, 4, 1]: 6295
[0, 3, 4, 1, 2]: 12543
[0, 3, 4, 2, 1]: 12451
[0, 4, 1, 2, 3]: 8398
[0, 4, 1, 3, 2]: 8442
[0, 4, 2, 1, 3]: 8303
[0, 4, 2, 3, 1]: 8283
[0, 4, 3, 1, 2]: 8386
[0, 4, 3, 2, 1]: 8243
[1, 0, 2, 3, 4]: 16464
[1, 0, 2, 4, 3]: 16585
[1, 0, 3, 2, 4]: 16550
[1, 0, 3, 4, 2]: 16744
[1, 0, 4, 2, 3]: 16700
[1, 0, 4, 3, 2]: 16566
[1, 2, 0, 3, 4]: 8140
[1, 2, 0, 4, 3]: 8375
[1, 2, 3, 0, 4]: 4142
[1, 2, 3, 4, 0]: 4222
[1, 2, 4, 0, 3]: 4185
[1, 2, 4, 3, 0]: 4180
[1, 3, 0, 2, 4]: 5598
[1, 3, 0, 4, 2]: 5658
[1, 3, 2, 0, 4]: 5492
[1, 3, 2, 4, 0]: 5563
[1, 3, 4, 0, 2]: 5530
[1, 3, 4, 2, 0]: 5587
[1, 4, 0, 2, 3]: 8311
[1, 4, 0, 3, 2]: 8307
[1, 4, 2, 0, 3]: 4105
[1, 4, 2, 3, 0]: 4122
[1, 4, 3, 0, 2]: 4172
[1, 4, 3, 2, 0]: 4217
[2, 0, 1, 3, 4]: 12464
[2, 0, 1, 4, 3]: 12541
[2, 0, 3, 1, 4]: 6163
[2, 0, 3, 4, 1]: 6295
[2, 0, 4, 1, 3]: 6385
[2, 0, 4, 3, 1]: 6280
[2, 1, 0, 3, 4]: 12551
[2, 1, 0, 4, 3]: 12462
[2, 1, 3, 0, 4]: 6345
[2, 1, 3, 4, 0]: 6271
[2, 1, 4, 0, 3]: 6197
[2, 1, 4, 3, 0]: 6459
[2, 3, 0, 1, 4]: 6081
[2, 3, 0, 4, 1]: 6278
[2, 3, 1, 0, 4]: 6230
[2, 3, 1, 4, 0]: 6178
[2, 3, 4, 0, 1]: 12487
[2, 3, 4, 1, 0]: 12558
[2, 4, 0, 1, 3]: 6308
[2, 4, 0, 3, 1]: 6259
[2, 4, 1, 0, 3]: 6383
[2, 4, 1, 3, 0]: 6249
[2, 4, 3, 0, 1]: 12325
[2, 4, 3, 1, 0]: 12642
[3, 0, 1, 2, 4]: 4224
[3, 0, 1, 4, 2]: 4081
[3, 0, 2, 1, 4]: 4168
[3, 0, 2, 4, 1]: 4119
[3, 0, 4, 1, 2]: 8224
[3, 0, 4, 2, 1]: 8417
[3, 1, 0, 2, 4]: 5601
[3, 1, 0, 4, 2]: 5543
[3, 1, 2, 0, 4]: 5591
[3, 1, 2, 4, 0]: 5501
[3, 1, 4, 0, 2]: 5563
[3, 1, 4, 2, 0]: 5632
[3, 2, 0, 1, 4]: 4133
[3, 2, 0, 4, 1]: 4228
[3, 2, 1, 0, 4]: 4147
[3, 2, 1, 4, 0]: 4079
[3, 2, 4, 0, 1]: 8314
[3, 2, 4, 1, 0]: 8276
[3, 4, 0, 1, 2]: 16676
[3, 4, 0, 2, 1]: 16819
[3, 4, 1, 0, 2]: 16499
[3, 4, 1, 2, 0]: 16666
[3, 4, 2, 0, 1]: 16656
[3, 4, 2, 1, 0]: 16659
[4, 0, 1, 2, 3]: 8342
[4, 0, 1, 3, 2]: 8462
[4, 0, 2, 1, 3]: 8182
[4, 0, 2, 3, 1]: 8356
[4, 0, 3, 1, 2]: 8341
[4, 0, 3, 2, 1]: 8389
[4, 1, 0, 2, 3]: 12358
[4, 1, 0, 3, 2]: 12566
[4, 1, 2, 0, 3]: 6261
[4, 1, 2, 3, 0]: 6152
[4, 1, 3, 0, 2]: 6263
[4, 1, 3, 2, 0]: 6270
[4, 2, 0, 1, 3]: 6206
[4, 2, 0, 3, 1]: 6271
[4, 2, 1, 0, 3]: 6157
[4, 2, 1, 3, 0]: 6228
[4, 2, 3, 0, 1]: 12544
[4, 2, 3, 1, 0]: 12569
[4, 3, 0, 1, 2]: 8383
[4, 3, 0, 2, 1]: 8493
[4, 3, 1, 0, 2]: 8329
[4, 3, 1, 2, 0]: 8228
[4, 3, 2, 0, 1]: 8359
[4, 3, 2, 1, 0]: 8391
https://ideone.com/3zSxLN
language:
D (dmd 2.085.0)
created:
7 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!