From 2f817e4dd7e7dd85541c31b3a030eee4662b48d7 Mon Sep 17 00:00:00 2001
From: William Carroll <wpcarro@gmail.com>
Date: Thu, 26 Mar 2020 16:57:41 +0000
Subject: Solve InterviewCake's recursive string permutations problem

Write a function that returns the set of all of the possible permutations of an
input string. This function should be solved recursively.
---
 .../part_two/recursive-string-permutations.ts      | 85 ++++++++++++++++++++++
 scratch/deepmind/part_two/todo.org                 |  2 +-
 2 files changed, 86 insertions(+), 1 deletion(-)
 create mode 100644 scratch/deepmind/part_two/recursive-string-permutations.ts

(limited to 'scratch')

diff --git a/scratch/deepmind/part_two/recursive-string-permutations.ts b/scratch/deepmind/part_two/recursive-string-permutations.ts
new file mode 100644
index 0000000000..cb930d9ad6
--- /dev/null
+++ b/scratch/deepmind/part_two/recursive-string-permutations.ts
@@ -0,0 +1,85 @@
+// Returns a new string comprised of every characters in `xs` except for the
+// character at `i`.
+function everyOtherChar(xs: string, i: number): string[] {
+  const result = [];
+
+  for (let j = 0; j < xs.length; j += 1) {
+    if (i !== j) {
+      result.push(xs[j]);
+    }
+  }
+
+  return [xs[i], result.join('')];
+}
+
+function getPermutations(xs: string): Set<string> {
+  if (xs === '') {
+    return new Set(['']);
+  }
+
+  const result: Set<string> = new Set;
+
+  for (let i = 0; i < xs.length; i += 1) {
+    const [char, rest] = everyOtherChar(xs, i);
+    const perms = getPermutations(rest);
+
+    for (const perm of perms) {
+      result.add(char + perm);
+    }
+  }
+
+  return result;
+}
+
+// Tests
+let desc = 'empty string';
+let input = '';
+let actual = getPermutations(input);
+let expected = new Set(['']);
+assert(isSetsEqual(actual, expected), desc);
+
+desc = 'one character string';
+input = 'a';
+actual = getPermutations(input);
+expected = new Set(['a']);
+assert(isSetsEqual(actual, expected), desc);
+
+desc = 'two character string';
+input = 'ab';
+actual = getPermutations(input);
+expected = new Set(['ab', 'ba']);
+assert(isSetsEqual(actual, expected), desc);
+
+desc = 'three character string';
+input = 'abc';
+actual = getPermutations(input);
+expected = new Set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']);
+assert(isSetsEqual(actual, expected), desc);
+
+desc = 'four character string';
+input = 'abca';
+actual = getPermutations(input);
+expected = new Set([
+  'abca', 'abac', 'acba', 'acab', 'aabc', 'aacb', 'baca', 'baac', 'bcaa',
+  'bcaa', 'baac', 'baca', 'caba', 'caab', 'cbaa', 'cbaa', 'caab', 'caba',
+  'aabc', 'aacb', 'abac', 'abca', 'acab', 'acba'
+]);
+assert(isSetsEqual(actual, expected), desc);
+
+function isSetsEqual(as, bs) {
+  if (as.size !== bs.size) {
+    return false;
+  }
+  for (let a of as) {
+    if (!bs.has(a)) return false;
+  }
+  return true;
+}
+
+function assert(condition, desc) {
+  if (condition) {
+    console.log(`${desc} ... PASS`);
+  } else {
+    console.log(`${desc} ... FAIL`);
+  }
+}
diff --git a/scratch/deepmind/part_two/todo.org b/scratch/deepmind/part_two/todo.org
index ee91e47551..ba128bb82d 100644
--- a/scratch/deepmind/part_two/todo.org
+++ b/scratch/deepmind/part_two/todo.org
@@ -28,7 +28,7 @@
 ** DONE MeshMessage
 ** DONE Find Repeat, Space Edition BEAST MODE
 * Dynamic programming and recursion
-** TODO Recursive String Permutations
+** DONE Recursive String Permutations
 ** TODO Compute nth Fibonacci Number
 ** TODO Making Change
 ** TODO The Cake Thief
-- 
cgit 1.4.1