Skip to content

Instantly share code, notes, and snippets.

@gkucmierz
Forked from bcherny/nth-permutation.js
Created August 20, 2017 16:17
Show Gist options
  • Save gkucmierz/2d9bbf12338e17d6e53361eef95ea421 to your computer and use it in GitHub Desktop.
Save gkucmierz/2d9bbf12338e17d6e53361eef95ea421 to your computer and use it in GitHub Desktop.
get nth permutation of a string
// (as: Array[Array[A]]) => Array[A]
function flatten (as) {
return as.reduce((a, b) => a.concat(b), [])
}
// (as: Array[A], a: A) => Array[A]
function without (as, a) {
const bs = as.slice(0)
bs.splice(as.indexOf(a), 1)
return bs
}
// (as: Array[A]) => Array[A]
function permute (as) {
switch (as.length) {
case 0: return []
case 1: return as
default: return flatten(as.map(a => permute(without(as, a)).map(b => a.concat(b))))
}
}
// (String) => Array[String]
const permuteString = _ => permute(_.split(''))
// (a: String, n: Number) => String
const nthPermutation = (a, n) => permuteString(a)[n]
console.assert(permuteString(''), [])
console.assert(permuteString('a'), ['a'])
console.assert(permuteString('ab'), ['ab', 'ba'])
console.assert(permuteString('abc'), ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
console.assert(nthPermutation('abcd', 6), 'bacd')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment