如何调整这段JavaScript代码,以打印出每个输入行上所有排列的句子?

3

因此,例如,如果我有以下输入:

I am the man

我想要恢复:

I am the man
I the man
I man
I the
I am
am the man
am man
am the
the man
man
man I
man I am
etc.

这是我目前为止对前20个输入句子的翻译:

            for (var i = 0; i < 20; i++) {
                var currWords = data[i].DisplayName.replace(/[^\x00-\x7F]/g, "").replace(/\(/g, "").replace(/\-/g, " ").replace(/\)/g, "").replace(/\*/g, "").toLowerCase().split(/\s+/g);

                for (var j = 0; j < currWords.length; j++) {
                    var currString = "";
                    for (var k = j; k < currWords.length; k++) {
                        currString += (currWords[k] + " ");
                    }
                    console.log(currString);
                }
            }

我只是想打印这些内容,以便复制到其他地方使用。目前它只能按顺序执行操作,我无法想到一种简单的方法来使其执行每个可能的句子。你有什么建议吗?


你想要一个特定的顺序吗? - ADreNaLiNe-DJ
没有。只有所有可能性。 - Team. Coco
这些不是你的句子的排列,而是所有子集的排列。 - Bergi
我的错,应该说的。 - Team. Coco
排列组合问题已经被研究透彻。请查阅任何算法书籍或者直接搜索互联网。 - user663031
2个回答

1

经过查看您的问题,我认为您可以采用Heap算法进行适应。

我使用位检查运算符编写和适应了这个算法,唯一的变化是我用它来构建字符串...

<!doctype html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>I am the man</title>
</head>
<body>
  <div id="output"></div>
  <script>
    p = m => {
      var a = m.split(' '),
      s = new Set(), l = a.length, ms, 
      b = (n=l) => {
        if (n == 1) {
          for ( let i = 1; i < 2**l; i++){
            ms = '';
            for ( let y = 0; y < l; y++){
              if (i & (1 << y)){
                ms += a[y]+" ";
              }
            }
          s.add(ms.trim());
          }
      } 
        else {
          for (let i=0;i<n;i++) {
            b(n - 1);
            [a[(n%2)*i],a[n-1]] = [a[n-1],a[(n%2)*i]];
          }
        }
      }
      b();
      return s;
    }
    test = p("I am the man")
    test.forEach(e => output.innerHTML += e + '<br>');
  </script>
</body>
</html>


谢谢。这正是我想要的! - Team. Coco

1

好的,这是一个关于创建排列的问题,可以是一个通用的问题,而不是针对JavaScript或特定句子的问题,有多种方法,让我简短地解释其中之一:

所以,你的句子"I am the man"有四个单词,首先将它们拆分成一个数组,例如

var words = "I am the man".split(" ")

所以你的数组有单词["I", "am", "the", "man"],并且length4,因为你有4个单词。 现在,如果要生成这些数字(1234)的排列,并使用每个结果的每个数字作为单词数组的索引并连接呢?感到困惑吗?让我解释一下。
假如我们可以生成一个像这样的数组 [1, 2, 3, 4, 12, 13, 14, 21, 23, 24, 41, 42, 43, 123, 124, ...., 4321] 然后从每个数字中构建一个句子:
例如:
1: "I"
4: "man"
43: "man the"
..
..
4321: "man the am I"

如果你对如何从数字生成这些字符串有疑问,我稍后会解释,现在不要忘记你已经有了单词数组。
现在,问题可能会出现,如果我们计算超过9个条目的排列呢?对于9,最大值将为987654321(因为我们将所有内容都视为数字),因此在所有情况下,我更喜欢构建一个数组而不是数字,因为最终我们需要拆分所有数字并从单词数组中获取索引,
所以,我更喜欢
[ [1],[2],[3],[4],[1,2],[1,3],...,[3,4,1],.........,[4,3,2,1] ]
而不是
[1,2,3,4,12,13,14,21,23,24,41,42,43,123,124,....,4321]
因为数字可能超过9,我们可以轻松处理它。

那么,现在的问题是如何构建数字数组(相信我,这是要做的最重要的事情,你的输出只是它的逻辑映射)

所以,如果我们通过像这样初始化一个数组来开始:[[1],[2],[3],[4]],直到长度为止,所以我们将从第2级开始,

我们将循环,从1到Length(即从1到4),并在每次迭代中迭代到每个数组,并检查该数组是否包含当前数字,如果没有,我们将切片该数组,并将当前数字推到开头,然后将其推回主结果数组。 我们还将传递每个数字数组,以便我们不需要查看整个数组,对于级别1,两者将是相同的,因此我们将通过slice()复制它,并且我们也将返回当前数字的数组。

function processEachDigit(length, mainArray, lastDigitArray) {
    var currDigitArray = [];
    var n;
    for (n = 1; n <= length; n++) {
        for (idx = 0; idx < lastDigitArray.length; idx++) {
            var eachArray = lastDigitArray[idx];
            if (!eachArray.includes(n)) {
                var newArr = eachArray.slice();
                newArr.unshift(n)
                mainArray.push(newArr);
                currDigitArray.push(newArr)
            }
        }
    }
return currDigitArray;
}

首次出现的是:

mainArray = [[1], [2], [3], [4]] //将通过循环进行初始化

以及

currDigitArray  = mainArray.slice()
//as we will keep update mainArray we cannot use the same reference

"我们将像这样调用它:"
processEachDigit(words.length, mainArray, currDigitArray)

所以主数组是

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

然后变成了

[[1], [2], [3], [4], [1, 2], [1,3], ......., [4,2], [4,3]]

并且返回第二个数字元素的数组,即

[[1,2], [1, 3], [1, 4], [2, 1], [2, 3]......., [4,2], [4,3]]

因此,我们将使用第二位数字数组来构建第三位数字数组,然后将第三位数字数组传递给构建第四位数字数组。

现在,我们真的需要最初构建单个数字数组吗?不需要。

传递一个空的数组将其创建为找不到任何元素,因此我们只需要将主数组初始化为空数组,当前数字数组初始化为空数组的数组,我只是用slice()等来解释我们正在尝试做什么。

我们开始吧

function getPermutationArray(L) {
var mainArr = [];
var n;
var currDigitArr = [[]];
    for(n=1;n<=L;n++) {
        currDigitArr = processEachDigit(L, mainArr, currDigitArr);
    }
return mainArr;
}

现在您可以调用getPermutationArray(<任何数字>)并返回该数组,现在尝试从该数组进行映射。如果失败,我会帮助您,这是一项简单的工作。
注意:我本可以写一个小代码段,但只是为了更好地解释它而写了这么多内容,而且可能有很多方法,我只尝试了其中之一,因为我不想使用递归,使用递归也可以实现此目标。如果有什么不清楚的地方,请留言。
祝编码愉快 :)

谢谢,经过研究后我决定制定另一个计划。这种方法向我展示了可能创建的排列数量。对于我需要的700行,它将创建近50万个排列。哎呀。 - Team. Coco

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接