Merge master

mgechev · mgechev · commit 13441bc986fc · 2017-05-13T09:50:48.000-07:00
diff --git a/src/others/minkowski-distance.js b/src/others/minkowski-distance.js
@@ -0,0 +1,79 @@
+(function (exports) {
+  'use strict';
+
+  var minkowskiDistance = (function () {
+
+    function chebyshevDistance (x, y, lx, p, mathfn) {
+      var ret = -p;
+      var i;
+
+      for (i = 0; i < lx; i += 1) {
+        ret = mathfn(ret, Math.abs(x[i] - y[i]));
+      }
+
+      return ret;
+    }
+
+    function minkowskiDistance (x, lx, y, ly, p) {
+      var d;
+      var i;
+
+      if (lx !== ly) {
+        throw 'Both vectors should have same dimension';
+      }
+
+      if (isNaN(p)) {
+        throw 'The order "p" must be a number';
+      }
+
+      if (p === Number.POSITIVE_INFINITY) {
+        return chebyshevDistance(x, y, lx, p, Math.max);
+      } else if (p === Number.NEGATIVE_INFINITY) {
+        return chebyshevDistance(x, y, lx, p, Math.min);
+      } else if (p < 1) {
+        throw 'Order less than 1 will violate the triangle inequality';
+      } else {
+        d = 0;
+
+        for (i = 0; i < lx; i += 1) {
+          d += Math.pow(Math.abs(x[i] - y[i]), p);
+        }
+
+        return isNaN(d)
+          ? 0
+          : Math.pow(d, 1 / p);
+
+      }
+
+    }
+
+    /**
+     * The Minkowski distance between two points gets generalized
+     * metric distance
+     * when p === 1, this becomes same as Manhattan Distance
+     * when p === 2, this becomes same as Euclidean Distance
+     * when p === Positive or Negative Infinity,
+     *  this becomes chebyshev distance
+     *
+     * @public
+     * @module others/minkowski-distance
+     *
+     * @example
+     * var dist = require('path-to-algorithms/src/others/' +
+     * 'minkowski-distance').minkowskiDistance;
+     * console.log(dist([0, 1], [1, 1], 2)); // 1
+     *
+     * @param {Array} x source point
+     * @param {Array} y target point
+     * @param {Number} p order of Minkowski distance
+     * @returns {Number} distance between two points, if distance
+     * is NaN, then this returns 0
+     */
+    return function (x, y, p) {
+      return minkowskiDistance (x, x.length, y, y.length, p);
+    };
+  }());
+
+  exports.minkowskiDistance = minkowskiDistance;
+
+}(typeof exports === 'undefined' ? window : exports));
diff --git a/src/shuffle/fisheryates.js b/src/shuffle/fisheryates.js
@@ -20,12 +20,9 @@
   function shuffle(array) {
     var size = array.length;
     var rand;
-    var temp;
     for (var i = 0; i < size; i += 1) {
       rand = Math.floor(i + Math.random() * (size - i));
-      temp = array[rand];
-      array[rand] = array[i];
-      array[i] = temp;
+      [array[rand], array[i]] = [array[i], array[rand]];
     }
     return array;
   }
diff --git a/test/others/minkowski-distance.spec.js b/test/others/minkowski-distance.spec.js
@@ -0,0 +1,42 @@
+'use strict';
+
+var mod = require('../../src/others/minkowski-distance.js');
+var minkowskiDistance = mod.minkowskiDistance;
+
+describe('Minkowski Distance', function () {
+  it('should return 1 with points (0, 1), (1, 1) in order 1.', function () {
+    expect(minkowskiDistance([0, 1], [1, 1], 1)).toBe(1);
+  });
+  it('should return 2 with points (0, 1), (1, 1) in order 2.', function () {
+    expect(minkowskiDistance([0, 1], [1, 1], 2)).toBe(1);
+  });
+  it('should return 2 with points (0, 1, 4), (1, 1, 6) in order Positive Infinity.', function () {
+    expect(minkowskiDistance([0, 1, 4], [1, 1, 6], Number.POSITIVE_INFINITY)).toBe(2);
+  });
+  it('should return 0 with points (0, 1, 4), (1, 1, 6) in order Negative Infinity.', function () {
+    expect(minkowskiDistance([0, 1, 4], [1, 1, 6], Number.NEGATIVE_INFINITY)).toBe(0);
+  });
+  it('should return 8.372966759705923 with points (0, 3, 4, 5), (7, 6, 3, -1) in order 3.', function () {
+    expect(minkowskiDistance([0, 3, 4, 5], [7, 6, 3, -1], 3)).toBe(8.372966759705923);
+  });
+  it('should throw when both vectors don\'t have same dimension', function () {
+    expect(function () {
+      minkowskiDistance([1, 2], [1], 1)
+    }).toThrow('Both vectors should have same dimension');
+  });
+  it('should throw when p is not defined', function () {
+    expect(function () {
+      minkowskiDistance([1, 2], [1, 2])
+    }).toThrow('The order "p" must be a number');
+  });
+  it('should throw when p is not a number', function () {
+    expect(function () {
+      minkowskiDistance([1, 2], [1, 2], NaN)
+    }).toThrow('The order "p" must be a number');
+  });
+  it('should throw when p is less than 1', function () {
+    expect(function () {
+      minkowskiDistance([1, 2], [1, 2], 0)
+    }).toThrow('Order less than 1 will violate the triangle inequality');
+  });
+});

Original file line number	Diff line number	Diff line change
`@@ -20,12 +20,9 @@`
`20`	`20`	`function shuffle(array) {`
`21`	`21`	`var size = array.length;`
`22`	`22`	`var rand;`
`23`		`- var temp;`
`24`	`23`	`for (var i = 0; i < size; i += 1) {`
`25`	`24`	`rand = Math.floor(i + Math.random() * (size - i));`
`26`		`- temp = array[rand];`
`27`		`- array[rand] = array[i];`
`28`		`- array[i] = temp;`
	`25`	`+ [array[rand], array[i]] = [array[i], array[rand]];`
`29`	`26`	`}`
`30`	`27`	`return array;`
`31`	`28`	`}`