Commits

Kenneth Jørgensen committed ddb79e4

Implemented integerArrayWithSum

  • Participants
  • Parent commits 548349b

Comments (0)

Files changed (4)

 {
 	"fullname": "RandomUtil",
 	"name": "random-util",
-	"version": "0.0.3",
+	"version": "0.0.4",
 	"description": "Randomness utility.",
 	"keywords": ["random", "prng"],
 	"homepage": "https://bitbucket.org/kennethjor/random-util",
 		"grunt-contrib-watch":      ">= 0.5.1",
 		"grunt-jessie":             ">= 0.0.2",
 		"grunt-coffeelint":         ">= 0.0.7",
-		"sinon":                    ">= 1.5.2"
+		"sinon":                    ">= 1.5.2",
+		"underscore":               ">= 1.5.1"
 	},
 	"engines": {
 		"node": ">= 0.8.0"
-/*! RandomUtil 0.0.2 - MIT license */
+/*! RandomUtil 0.0.3 - MIT license */
 (function() {
   var RandomUtil, abs, exports, floor, pow, root,
     __hasProp = {}.hasOwnProperty;
   root = this;
 
   RandomUtil = {
-    version: "0.0.2"
+    version: "0.0.3"
   };
 
   if (typeof exports !== "undefined") {
     throw new Error("This should never happen, r was " + r);
   };
 
+  RandomUtil.integerArrayWithSum = function(n, sum) {
+    var arr, i, _i, _j, _ref, _ref1;
+    arr = [];
+    for (i = _i = 0, _ref = n - 2; 0 <= _ref ? _i <= _ref : _i >= _ref; i = 0 <= _ref ? ++_i : --_i) {
+      arr[i] = this.randomInt(0, sum);
+    }
+    arr[n - 1] = sum;
+    arr = arr.sort(function(a, b) {
+      return a - b;
+    });
+    for (i = _j = _ref1 = n - 1; _ref1 <= 1 ? _j <= 1 : _j >= 1; i = _ref1 <= 1 ? ++_j : --_j) {
+      arr[i] -= arr[i - 1];
+    }
+    return arr;
+  };
+
 }).call(this);

spec/RandomUtilSpec.coffee

+_ = require "underscore"
 sinon = require "sinon"
 
 RandomUtil = require "../random-util"
 
+# Custom matcher to check for uniform arrays.
+toBeUniformlyDistributed = () ->
+	arr = @actual
+	# Calc sum.
+	sum = 0
+	for own i, v of arr
+		sum += v
+	# Calc share.
+	share = []
+	for own i, v of arr
+		share.push arr[i] / sum
+	# Calc error.
+	error = 0
+	for v in share
+		error += Math.pow( v - 1 / share.length , 2 )
+	error /= share.length
+	if _.isNaN error
+		console.log arr, error
+		throw new Error "Failed to calculate error"
+	if error > 0.01
+		notText = if @isNot then "not" else ""
+		@message = do (arr, error, notText) -> -> "Expected #{jasmine.pp arr} #{notText}to be uniformly distributed. Error was #{error}"
+		return false
+	return true
+
+
 describe "RandomUtil", ->
 	state = null
 	precision = null
 	increment = null
 
 	beforeEach ->
+		@addMatchers toBeUniformlyDistributed: toBeUniformlyDistributed
 		precision = 4
 		state = 0.0
 		increment = 0.1
 			v = RandomUtil.randomInt 5, 9
 			generated[v] or= 0
 			generated[v]++
-		for own i, v of generated
-			generated[i] = v/n
-		expect(generated[5]).toBeCloseTo 1/5, 2
-		expect(generated[6]).toBeCloseTo 1/5, 2
-		expect(generated[7]).toBeCloseTo 1/5, 2
-		expect(generated[8]).toBeCloseTo 1/5, 2
-		expect(generated[9]).toBeCloseTo 1/5, 2
+		generated[8] *= 2
+		expect(generated).toBeUniformlyDistributed()
 
 	it "should generate random numbers", ->
 		expect(RandomUtil.randomNumber 10, 15).toBeCloseTo 10.0, precision
 		expect(RandomUtil.weighted obj).toBe "d"
 		expect(RandomUtil.weighted obj).toBe "d"
 		expect(RandomUtil.weighted obj).toBe "d"
+
+	it "should generate a random array of integers which sum to a constant", ->
+		RandomUtil.random = Math.random
+		n = 1000
+		sum = 20
+		vals = 5
+		uniform = []
+		for i in [0..vals - 1]
+			uniform[i] = 0
+		for i in [1..n]
+			# Generate.
+			arr = RandomUtil.integerArrayWithSum vals, sum
+			# Check count.
+			expect(arr.length).toBe 5
+			# Check sum and constraints.
+			s = 0
+			for i in arr
+				expect(i).toBeGreaterThan -1
+				expect(i).toBeLessThan sum + 1
+				s += i
+			expect(s).toBe sum
+			# Add to uniform check.
+			for i in [0..vals - 1]
+				uniform[i] += arr[i]
+		expect(uniform).toBeUniformlyDistributed()
+

src/RandomUtil.coffee

 		if current > pos
 			return i
 	throw new Error "This should never happen, r was #{r}"
+
+# Creates an array with `n` elements such that the sum of all elements equals `sum`.
+# Code based on `ojr_array_with_sum` from `ojrandlib`.
+RandomUtil.integerArrayWithSum = (n, sum) ->
+	arr = []
+	for i in [0..n - 2]
+		arr[i] = @randomInt 0, sum
+	arr[n - 1] = sum
+	arr = arr.sort (a, b) -> return a - b
+	for i in [n - 1..1]
+		arr[i] -= arr[i - 1]
+	return arr