非常长的排列 – 句子的字谜

我有一个近2700个string的数组，我需要为一个句子的anagramfind正确的短语。 该列表是一个有序的列表，其中包含几乎10万条长的单词列表。

而且我想把它们分成1,2和3个单词，如果它们符合我的长度，就可以匹配单词的长度。

我试过这个function，但在内存上失败了，我可以设置最多3个单词在一起匹配：

var permutations = require('./permutations.js').permutations; var shortList = words.slice(10, 20); var result = permutations(shortList); console.log(result); 

这在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)); 

编辑：

例

 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

所有3个单词的排列是3！ = 6

100,000字的所有组合select3是100000！ / 6（99,996！）〜= 1.66e14

所以你的最终输出将是1.66e14 * 6〜= 9.99e14

试图创build一个1万亿字节的string数组列表不止是您的计算机可以处理的列表。

我试过这个function，但是在内存上失败了

是一个轻描淡写

---

你将不得不对你的单词列表做一些预处理。 通过它们包含的字母和长度对它们进行分区。 然后做一个更集中的search你的字谜。

最后，不要为此使用recursion（这不是必要的，因为每次调用都会创build堆栈帧，所以它会更快用完。

只要循环使用三次ijk循环你就可以得到每一个结果 – 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

不重复长度为三的排列：

 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>');