Very long permutations - sentence anagram

Question

I have an array of almost 2700 strings, i need to find the correct phrase for a sentence anagram. The list is a sorted list, of almost 100k item long list of words that would fit.

And i want to combine them in 1, 2 & 3 words together and match on length of the words if they fit my length of my anagram, trimmed for whitespaces.

I tried this function but it fails on memory, could i set a max of 3 words together to match on:

var permutations = require('./permutations.js').permutations;

var shortList = words.slice(10, 20);

var result = permutations(shortList);
console.log(result);

and this in permutation.js

(function (exports) {
  'use strict';
  var permutations = (function () {
    var res;
    function swap(arr, i, j) {
      var temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
    function permutations(arr, current) {
      if (current >= arr.length) {
        return res.push(arr.slice());
      }
      for (var i = current; i < arr.length; i += 1) {
        swap(arr, i, current);
        permutations(arr, current + 1);
        swap(arr, i, current);
      }
    }
    return function (arr) {
      res = [];
      permutations(arr, 0);
      var temp = res;
      // Free the extra memory
      res = null;
      return temp;
    };
  }());
  exports.permutations = permutations;
}((typeof window === 'undefined') ? module.exports : window));

EDIT:

Example

var input = ['test', 'foo', 'bar', 'hello', 'world'];

var output = magicFunc(input);
// console.log(output);
//
// [['test foo bar'],
//  ['test foo hello'],
//  ['test foo world'],
//  ['test bar foo'],
//  ['test bar hello'],
//  ['test bar world']...];

Answer 1

All permutations of 3 words is 3! = 6

All combinations of 100,000 words pick 3 is 100000! / 6(99,996!) ~= 1.66e14

So your final output would be 1.66e14 * 6 ~= 9.99e14

Trying to create a list of 1 quadrillion string arrays is more than your computer can handle.

I tried this function but it fails on memory

Is an understatement

---

You are going to have to do some preprocessing on your list of words. Partition them by what letters they contain and their length. Then do a more focused search for your anagrams.

Finally, don't use recursion for this (it's not necessary and it will use up meory faster because of the stack frames being created for every call.

just use for loop three times i j k looping you you can get every result – Daniel Cheung

for(var i = 0; i < list.length; i++) {
  var wi = list[i];
  for(var j = i + 1; j < list.length; j++) {
    var wj = list[j];
    for(var k = j + 1; k < list.length; k++) {
      var wk = list[k];
      // hard coded 6 permutations
      var p1 = wi + wj + wk;
      var p2 = wi + wk + wj;
      var p3 = wj + wi + wk;
      var p4 = wj + wk + wi;
      var p5 = wk + wi + wj;
      var p6 = wk + wj + wi;
      // check p1 - p6 for your anagram condition
      ...
    }
  }
}

Answer 2

Permutation without repetition with length of three:

var input = ['test', 'foo', 'bar', 'hello', 'world'],
    output = input.reduce(function (r, a, i) {
        input.forEach(function (b, j) {
            i !== j && input.forEach(function (c, k) {
                i !== k && j !== k && r.push([a, b, c]);
            });
        });
        return r;
    }, []);
document.write('<pre>' + JSON.stringify(output, null, 4) + '</pre>');