Travelling Salesman Sketches: Drawing Permutations

index.html

<header>
  <input type="range" list="numbers" value="5">
  <datalist id="numbers">
    <option>3</option>
    <option>5</option>
    <option>10</option>
    <option>25</option>
    <option>50</option>
    <option>100</option>
  </datalist>
</header>
<div>
  <canvas id="cvs1" height="800" width="800"></canvas>
  <canvas id="cvs2" height="800" width="800"></canvas>
</div>
<footer>
  <p>Permutation</p>
  <p id="perm"></p>
</footer>

script.babel

console.clear();
const PI = Math.PI;
const PI2 = PI * 2;

class Point {
  constructor() {
    this.x = Math.random();
    this.y = Math.random();
    this.prox = Math.hypot(0.5 - this.x, 0.5 - this.y);
  }
}

class Permutations {
  constructor(pointCount) {
    this.pointCount = pointCount;
    this.data = [];
    // initial array ignores 0. we start permutations at 1.
    for (let i = 1; i <= this.pointCount - 1; i++) this.data.push(i);
    this.originalData = Array.from(this.data);
  }
  
  next() {
    let more = this.nextPermutation(this.data);
    if (!more) this.data = Array.from(this.originalData);
    return this.current();
  }

  load(idx) {
    return this.current()[idx];
  }

  current() {
    return [0].concat(this.data).concat([0]);
  }

  // https://stackoverflow.com/a/34014930
  nextPermutation(array) {
    // Find non-increasing suffix
    let i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) i--;
    if (i <= 0) return false;

    // Find successor to pivot
    let j = array.length - 1;
    while (array[j] <= array[i - 1]) j--;
    let temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;

    // Reverse suffix
    j = array.length - 1;
    while (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++; j--;
    }
    return true;
  }
}

class Canvas {
  constructor() {
    this.element1 = document.querySelector('#cvs1');
    this.context1 = this.element1.getContext('2d');
    this.element2 = document.querySelector('#cvs2');
    this.context2 = this.element2.getContext('2d');
    this.gutter = 30;
    this.diameter = this.element1.width;
    this.switchContext(0);
  }

  clear(which) {
    if (which !== undefined) {
      [this.context1, this.context2][which].clearRect(0, 0, this.diameter, this.diameter);
    } else {
      this.context1.clearRect(0, 0, this.diameter, this.diameter);
      this.context2.clearRect(0, 0, this.diameter, this.diameter);
    }
  }

  switchContext(idx) {
    this.context = [this.context1, this.context2][idx];
  }

  text(x, y, text, offset = 1) {
    this.context.textAlign = 'center';
    this.context.textBaseline = 'middle';
    let fontSize = 14;
    let offsetY = (y > 0.5) ? fontSize * (offset * 1.5) : fontSize * (offset * -1.5);
    this.context.fillStyle = 'white';
    this.context.font = `${fontSize}px Helvetica`;
    this.context.fillText(text, this.relative(x), this.relative(y) + offsetY);
  }

  rect(x, y, w, h, color = 'red') {
    this.context.strokeStyle = color;
    this.context.strokeRect(
      this.relative(x), this.relative(y), 
      this.relativeSize(w), this.relativeSize(h)
    );
  }

  point(x, y, fill = 'red') {
    this.context.fillStyle = fill;
    this.context.beginPath();
    this.context.arc(this.relative(x), this.relative(y), 4, 0, PI2);
    this.context.fill();
  }
  
  path(x1, y1, x2, y2, stroke = 'red') {
    this.context.strokeStyle = stroke;
    this.context.lineWidth = 2;
    this.context.beginPath();
    this.context.moveTo(this.relative(x1), this.relative(y1));
    this.context.lineTo(this.relative(x2), this.relative(y2));
    this.context.stroke();
  }
  
  relativeSize(size) {
    return size * (this.diameter - this.gutter * 2);
  }

  relative(plot) {
    return this.relativeSize(plot) + this.gutter;
  }
}

class Drawer {
  constructor() {
    this.canvas = new Canvas();
    this.$perm = document.querySelector('#perm');
    this.draw();
  }

  run(points) {
    this.speed = 12;
    this.points = points;
    this.points = this.points.sort((a, b) => {
      if (a.prox > b.prox) return -1;
      if (a.prox < b.prox) return 1;
      return 0;
    });
    this.permutations = new Permutations(points.length);
    this.pointCount = this.permutations.data.length + 2;
    this.write();
    this.pointIdx = 0;
    this.progress = 0;
  }

  write() {
    this.$perm.innerHTML = this.permutations.current().join(', ');
  }

  draw() {
    if (this.points) {
      this.canvas.clear(1);
      if (this.pointIdx % this.pointCount === 0) {
        this.canvas.clear();
        this.canvas.switchContext(0);
        this.points.forEach((point) => {
          this.canvas.point(point.x, point.y, '#222');
        });
        this.canvas.switchContext(1);
        this.write();
      }
      let idx1 = this.permutations.load(this.pointIdx % this.pointCount);
      let point1 = this.points[idx1];
      let idx2 = this.permutations.load(((this.pointIdx % this.pointCount) + 1) % this.pointCount);
      let point2 = this.points[idx2];
      let x1 = point1.x,
          y1 = point1.y;
      let x2 = point2.x,
          y2 = point2.y;
      if ((this.pointIdx + 1) % this.pointCount > 0) {
        let ratio = (this.progress % this.speed) / (this.speed - 1);
        let distX = (x1 - x2) * ratio;
        let distY = (y1 - y2) * ratio;
        let dx = x1 - distX;
        let dy = y1 - distY;


        this.canvas.switchContext(1);
        this.canvas.path(x1, y1, dx, dy, 'red', 2);
        this.canvas.point(x1, y1, 'red');
        
        this.canvas.switchContext(1);
      }
      this.progress++;
      if (this.progress % this.speed === 0) {
        this.canvas.switchContext(0);
        this.canvas.path(x1, y1, x2, y2, '#222', 2);
        this.canvas.point(x1, y1, '#222'); // previous
        this.pointIdx++;
        if (this.pointIdx % this.pointCount === 0) {
          this.permutations.next();
        }
      }
    }

    window.requestAnimationFrame(this.draw.bind(this));
  }
}

class AwesomePossum {
  constructor() {
    this.drawer = new Drawer();
  }

  run(pointCount) {
    this.points = [];
    this.pointCount = pointCount;
    for (let i = 0; i < this.pointCount; i++) {
      this.points.push(new Point());
    }
    this.drawer.run(this.points);
  }
}

let app = new AwesomePossum();
let $range = document.querySelector('input');

document.body.addEventListener('click', run);
$range.addEventListener('change', run);
run();

function run() {
  app.run(parseInt($range.value));
}

style.scss

body {
  background: #121212;
}

header,
footer {
  text-align: center;
  margin: 1rem 0;
  color: #F00;
  font-weight: 300;
  font-size: 0.8rem;
  p#perm {
    color: #999;
    width: 95%;
    max-width: 600px;
    margin: 0 auto;
  }
  ul {
    list-style: none;
    padding: 0;
  }
}
div {
  position: relative;
  width: 95%;
  max-width: 600px;
  margin: 1rem auto;
  cursor: pointer;
  &:after {
    content: '';
    padding-bottom: 100%;
    display: block;
  }
  canvas {
    &:first-child {
      background: black;
    }
    position: absolute;
    top: 0; left: 0;
    width: 100%;
    height: auto;
  }
}

travelling-salesman-sketches-drawing-permutations.markdown

Travelling Salesman Sketches: Drawing Permutations

Drawing all the permutations of the ordering of a group of nodes.

The permutation count could be cut in half to eliminate reverse order permutations. eg 01230 === 03210.

A Pen by HARUN PEHLİVAN on CodePen.

License.