34 a more declarative permutation & combination

p&c.js

// a more declarative algorithm for finding permutations & combinations of a sequence

// first, we introduce a higher-order fuction: flat-map
// it works like map, but will flatten the result by one level (only one level, not recursive)
// ex.
//   - map the procedure (x) => [x, 2 * x] onto array [1, 2, 3] will produce
//   a 2-dimensional array [[1, 2], [2, 4], [3, 6]]
//   - instead, flat-map the procedure (x) => [x, 2 * x] onto array [1, 2, 3] will produce
//   a flattened 1-dimensional array [1, 2, 2, 4, 3, 6]
function flatMap(arr, proc) {
  return flatten(map(arr, proc))
}

function flatten(arr) {
  return arr.reduce((a, b) => {
    return a.concat(b)
  }, [])
}

function map(arr, proc) {
  return arr.map(proc)
}

// then, the permutation algorithm can be described as:
// for a sequence, apply the following procedure to it with flat-map
//   to form new permutations from previous permutations
//     choose an element as head and make other elements as tail
//     recursively premute tail to get a bunch of permutations
//     use map to attach the head to every permutations to get the result
function permute(arr) {
  if (arr.length == 0) {
    return [[]]
  } else if (arr.length == 1) {
    return [arr]
  } else {
    return flatMap(arr, (e, i) => {
      var head = e
      var tail = arr.slice()
      tail.splice(i, 1)
      var permuted = permute(tail)
      return map(permuted, (solution) => {
        return [head].concat(solution)
      })
    })
  }
}

// and, the combination algorithm can be described as:
// choose the first element from the sequence as head and make other elements as tail
// recursively call combine to get combinations
// then apply the following procedure to combinations with flat-map
//   to form new combinations from previous combinations
//     the first choice is to take the head and combine it into the result
//     the second choice is not to take the head and use the original combination as the result
function combine(arr) {
  if (arr.length == 0) {
    return [[]]
  } else {
    var head = arr.slice(0, 1)
    var tail = arr.slice(1)
    var combined = combine(tail)
    return flatMap(combined, (comb) => {
      var untake = comb
      var take = [head].concat(comb)
      return [untake, take]
    })
  }
}

// test
var arr = ['a', 'b', 'c', 'd']
var permuted = permute(arr)
var combined = combine(arr)
console.log(combined)
console.log(permuted)