Recursively going through permutations without storing in memory

Question

I'm trying to go through all possible permutations of an array using a recursive function. The permutations don't need to be stored in memory. They are being processed right away by the recursive function.

The idea is that the recursive function has an argument 'used' which keeps track of the elements that are 'fixed' at this point in the recursion tree, and an argument 'free' which keeps track of the elements that are not fixed yet at this point (i.e. they will be rearranged in the recursion steps going down the tree from there). So the first time, the function is called with an empty 'used' array and a full 'free' array.

Somehow my code below doesn't work yet. It only processes the first permutation successfully.

const elements = [7, 23, 41, 65, 99]
const n = elements.length;

handlePermutations([], elements);

function handlePermutations(used, free) {
  if (used.length<n) {
    for (i = 0; i < free.length; i++) {
      newUsed = used.concat(free[i]);           // add element i from free to used
      newFree = free.filter(x => x != free[i])  // remove element i from free
      handlePermutations(newUsed, newFree);
    }
  } else {        
    // ... 'process' this permutation (do something useful with it) ...
  }
}

Answer 1

You're using (implicitly declared) global i, so it doesn't reset for each functions.

change it to let i fix the problem

const elements = [7, 23, 41, 65, 99]
const n = elements.length;

handlePermutations([], elements);

function handlePermutations(used, free) {
  if (used.length < n) {
    for (let i = 0; i < free.length; i++) {
      let newUsed = used.concat(free[i]); // add element i from free to used
      let newFree = free.filter(x => x != free[i]) // remove element i from free
      handlePermutations(newUsed, newFree);
    }
  } else {
    console.log(...used)
    // ... 'process' this permutation (do something useful with it) ...
  }
}

---

btw, your current free.filter(...) breaks if you have duplicate items. One possible way is simply change it to check passed in index.

free.filter((x,index) => index!=i)

Answer 2

Out of interest, here is a generator version of the same algorithm (with some changes).

const elements = [1, 2, 3, 4, 5]

for (let item of Permutations(elements)) {
  console.log(...item)
}

// note: this (OP's) algorithm use O(n**2) space afaict 
function Permutations(elements) {
  return handlePermutations([], elements)

  function* handlePermutations(used, free) {
    if (free.length == 0)
      yield used;
    else {
      for (let i = 0; i < free.length; i++) {
        let newUsed = used.concat(free[i]) // add element i from free to used
        let newFree = free.filter((x, index) => index != i) // remove element i from free
        yield* handlePermutations(newUsed, newFree);
      }
    }
  }
}

Answer 3

Another approach has you pass the callback function that will be used with each permutation.

const excludeIndex = (i) => (xs) => 
  [... xs .slice (0, i), ... xs .slice (i + 1)]

const handlePermutations = (fn) => (free, used = []) =>
  free.length == 0
    ? fn (used)
    : free .forEach (
        (e, i) => handlePermutations (fn) (excludeIndex (i) (free), [...used, e])
      )

handlePermutations (xs => console. log(...xs)) ([7, 23, 41, 65])

.as-console-wrapper {max-height: 100% !important; top: 0}

We include the simple helper excludeIndex, which returns a copy of the array with the index missing. We use that in the recursive call along with the concatenation of the current element to used.

I'm not much of a fan of code written only for side-effects, but as that is the fundamental goal in the question, I can certainly live with it here.

Time complexity is unavoidably O (n!). Space complexity I think is O (n), since free and used together hold the original n elements. (Oops, see the comments!) Space complexity is O (n^2)

Answer 4

A different approach to this. Using a single integer to determine a distinct permutation of that array.

So generating all permutations for an array and processing them would be:

function permutation(array, n) {
  let result = array.slice(); // don't mutate the input
  for (let i = 0, rest = result.length; rest > 1 && n > 0; ++i, n = Math.floor(n / rest--)) {
    let j = n % rest + i;
    if (i === j) continue;
    const tmp = result[i];
    result[i] = result[j];
    result[j] = tmp;
  }
  return result;
}

const elements = [1, 2, 3, 4, 5];
const length = elements.reduce((a,_,i) => a*(i+1), 1);
//const length = 5 * 4 * 3 * 2 * 1;

const map = {};
for (let i = 0; i <= length; ++i) {
  map[i] = permutation(elements, i).join();
}

console.log(map);
console.log("map[120] === map[0]", "We're back at the start. From now on this will just loop the results.");
console.log("expected %i, got %i (different values/permutations in the results)", length, new Set(Object.values(map)).size);

.as-console-wrapper{top:0;max-height:100%!important}

You said without storing. I'm using the map above because this snippet would only store the last 50 console.logs while it shows all 120 entries/lines in the map. And to show at the end that it creates no duplicates, that there are indeed 120 different permutations in that map.

Answer 5

You could take a simplified approach and hand over just an array of indices and take two rules:

• If the last element is greater then the previous element, swap both.

• Search for an index from the end of the array where the element is greater than left and right element.

  If found, search for the next grater element on the right side of the found index inclusive of the actual index, take this as new element in front of the group, sort the rest and apply.

  If not found, end recursion.

function next([...array]) {
    console.log(...array);
    if (array[array.length - 2] < array[array.length - 1]) {
        [array[array.length - 2], array[array.length - 1]] = [array[array.length - 1], array[array.length - 2]];
        return next(array);
    }
    let index = array.length - 1;
    while (--index) {
        if (array[index - 1] < array[index] && array[index] > array[index + 1]) {
            let value = Math.min(...array.slice(index - 1).filter(v => v > array[index - 1]))
            array = [
              ...array.slice(0, index - 1),
              value,
              ...array.slice(index - 1).filter(v => v !== value).sort((a, b) => a - b)
            ];
            break;
        }
    }
    if (!index) return;

    return next(array);
}

next([0, 1, 2, 3, 4]);

.as-console-wrapper { max-height: 100% !important; top: 0; }