1

我有一个包含近 2700 个字符串的数组，我需要为句子字谜找到正确的短语。该列表是一个排序列表，包含近 100k 项长的适合单词的列表。

我想将它们组合成 1、2 和 3 个单词，如果它们适合我的字谜长度，则匹配单词的长度，并修剪空格。

我尝试了这个功能，但它在内存上失败了，我可以设置最多 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']...];
4

2 回答 2

1

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

100,000个单词的所有组合选择3是100000！/ 6(99,996!) ~= 1.66e14

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

试图创建一个包含 1 万亿个字符串数组的列表超出了您的计算机可以处理的范围。

我试过这个功能，但它在内存上失败了

是轻描淡写

您将不得不对您的单词列表进行一些预处理。按它们包含的字母和长度对它们进行分区。然后对你的字谜进行更集中的搜索。

最后，不要为此使用递归（这不是必需的，因为每次调用都会创建堆栈帧，它会更快地耗尽内存。

只需使用 for 循环 3 次 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
      ...
    }
  }
}
于 2015-08-14T14:11:53.350 回答
0

长度为三的无重复排列：

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

于 2015-08-14T15:05:42.793 回答