I've managed to do this in two recursive functions. But am really curious, is it possible to use both recursions in one function...

Here is a task of an exercise and a hint:

Write a function called subsets that will return all subsets of an array.

Examples below.

Hint: For subsets([1, 2, 3]), there are two kinds of subsets:

1. Those that do not contain 3 (all of these are subsets of [1, 2]).
2. For every subset that does not contain 3, there is also a corresponding subset that is the same, except it also does contain 3.

Here is my solution with 2 recursives, examples of the task are included:

let arr = []
console.log(subsets(arr)); // [[]]
arr = [1]
console.log(subsets(arr)); // [[], [1]]
arr = [1,2]
console.log(subsets(arr)); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(subsets(arr)); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

// your code here
function subsets(arr) {
  if (arr.length === 0) return [[]]; // base

  let el = arr.slice(-1)
  let prev = subsets(arr.slice(0, -1))
  return prev.concat(addEl(prev,el))
  //can be instead iterative: return prev.concat(prev.map(x => x.concat([el])));  
}

function addEl(arrA, el) {
  let firstEl = arrA[0];
  let rest = arrA.slice(1)

  if (arrA.length === 1) return [firstEl.concat(el)]; // base

  return [firstEl.concat(el)].concat(addEl(rest, el)) 
}

CodePudding user response：

You were quite close already with the commented-out code, you just needed to use x.concat(el) instead of x.concat([el]). Or alternatively, el = arr.at(-1) instead of el = arr.slice(-1).

let arr = []
console.log(subsets(arr)); // [[]]
arr = [1]
console.log(subsets(arr)); // [[], [1]]
arr = [1,2]
console.log(subsets(arr)); // [[], [1], [2], [1, 2]]
arr = [1,2,3]
console.log(subsets(arr)); // [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

// your code here
function subsets(arr) {
  if (arr.length === 0) return [[]]; // base

  let el = arr.slice(-1)
  let prev = subsets(arr.slice(0, -1))
  return prev.concat(prev.map(x => x.concat(el)));  
}

CodePudding user response：

recursive generator

To get a lazy iterable of the subsets, you can use a recursive generator. A utility tee function is used to "branch" the iterable -

function *subsets(arr) {
  if (arr.length === 0) return yield []
  const last = arr.slice(-1)
  const [exclude, include] = tee(subsets(arr.slice(0, -1))) // recursive
  yield *exclude
  for (const s of include) yield s.concat(last)
}

function *tee(g, n = 2) {
  const memo = []
  function* iter(i) {
    while (true) {
      if (i >= memo.length) {
        const w = g.next()
        if (w.done) return
        memo.push(w.value)
      }
      else yield memo[i  ]
    }
  }
  while (n-- >= 0) yield iter(0)
}

console.log(JSON.stringify(Array.from(subsets([]))))
console.log(JSON.stringify(Array.from(subsets([1]))))
console.log(JSON.stringify(Array.from(subsets([1,2]))))
console.log(JSON.stringify(Array.from(subsets([1,2,3]))))

.as-console-wrapper { min-height: 100%; top: 0; }

[[]]
[[],[1]]
[[],[1],[2],[1,2]]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

persistent iterators

Above we use tee to read an iterable's values multiple times. Below we show iter that wraps a generator in a persistent iterator interface, allowing us to use the iterator multiple times.

function *subsets(arr) {
  if (arr.length === 0) return yield []
  const last = arr.slice(-1)
  const r = iter(subsets(arr.slice(0, -1))) // assign r
  yield *r // read from r
  for (const s of r) yield s.concat(last) // read from r again
}

For that we write an iter abstraction -

function iter(g) {
  let computed = memo(_ => g.next())
  return {
    get done() {
      return computed().done
    },
    get value() {
      return computed().value
    },
    next: memo(_ =>
      computed() && iter(g)
    ),
    *[Symbol.iterator]() {
      let t = this
      while(!t.done) {
        yield t.value
        t = t.next()
      }
    }
  }
}

Which depends on a memo abstraction -

function memo(f) {
  const nil = Symbol()
  let computed = nil
  return _ => {
    if (computed === nil)
      computed = f()
    return computed
  }
}

Hopefully you can begin to see how data abstraction allows us to write higher-level programs and keep complexity under control.

function *subsets(arr) {
  if (arr.length === 0) return yield []
  const last = arr.slice(-1)
  const r = iter(subsets(arr.slice(0, -1))) // recursive
  yield *r
  for (const s of r) yield s.concat(last)
}

function iter(g) {
  let computed = memo(_ => g.next())
  return {
    get done() {
      return computed().done
    },
    get value() {
      return computed().value
    },
    next: memo(_ =>
      computed() && iter(g)
    ),
    *[Symbol.iterator]() {
      let t = this
      while(!t.done) {
        yield t.value
        t = t.next()
      }
    }
  }
}

function memo(f) {
  const nil = Symbol()
  let computed = nil
  return _ => {
    if (computed === nil)
      computed = f()
    return computed
  }
}

console.log(JSON.stringify(Array.from(subsets([]))))
console.log(JSON.stringify(Array.from(subsets([1]))))
console.log(JSON.stringify(Array.from(subsets([1,2]))))
console.log(JSON.stringify(Array.from(subsets([1,2,3]))))

.as-console-wrapper { min-height: 100%; top: 0; }

[[]]
[[],[1]]
[[],[1],[2],[1,2]]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]