求解nPr (排列)的算法。为假人

Question

是的，我有RTFM。或者，在这种情况下，RTFSO。如果它出现在"npr“或”置换“的搜索结果中，我就读到了。虽然我已经实现了Heap的算法，但我不能从那里(所有排列)跳到nPr (长度r的所有排列，从一个更大的集合n中)。

实际的算法(伪代码很好)比不包括实际代码的冗长解释更可取。如果你想教我这个理论，好吧，我很乐意向它学习，但我也想要附带的代码。如果你能从堆的角度来看的话，太好了，否则，我会混过去的。

我没有任何代码要向您展示(除非您希望看到Heap在VBScript中实现(这是我在工作中所要处理的全部内容)，因为，正如我所说的，我不知道从那里得到集合n的每个r长度子集。

如果我缺少对nPr的描述，下面是一个非常简单的示例，说明我希望做什么：

考虑到背景..。

A、B、C

...I希望找到每一个两个字符的排列，如下所示：

a.b

A C

B-C

这个例子过于简单，因为我真正想要导出的是一个采用集合(数组)的广义解决方案，以及每个置换中应该包含的项数，作为调用参数。

Hmmm...now，我把所有这些都写出来了，在我看来，我只需要知道如何从集合n导出长度r的所有子集，因为我可以使用Heap找到这些子集的排列。

FYI:今年我50岁，这不是家庭作业。

Answer 1

相对简单的递归：

• 对于集合中的每个元素，不管是否使用它。
• 这两个变体的集合的其余部分都是递归的。
• 当结果完成或其余集为空时停止。
• 为了提高性能，避免使用开始/位置索引进行实际设置操作。

在JavaScript中：

function nPr(set, n) {
  nPrImpl(set, 0, new Array(n), 0);
}

function nPrImpl(set, pos, result, resultPos) {

  // result complete
  if (resultPos == result.length) {
    window.console.log(result);
    return;
  } 

  // No more characters available
  if (pos >= set.length) {
    return;
  }

  // With set[pos]
  result[resultPos] = set[pos];
  nPrImpl(set, pos + 1, result, resultPos + 1);

  // Without
  nPrImpl(set, pos + 1, result, resultPos);
}

// Test:
nPr(['A', 'B', 'C'], 2);

输出：

["A", "B"]
["A", "C"]
["B", "C"]

演示：https://tidejnet.appspot.com/v3/#id=8ht8adf3rlyi