求解 nPr（排列）的算法。对于傻瓜

Question

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

一个实际的算法（伪代码也可以）比一个不包括实际代码的冗长解释更受欢迎。如果你想教我理论，好吧，我很乐意从中学习，但我也想要附带的代码。如果你能把Heap的术语放进去，太好了；否则，我会蒙混过关。

我没有任何代码可以向您展示（除非您想看到Heap在VBScript中实现（这是我在工作中必须使用的全部）），因为正如我所说，我不知道从哪里去获取set n的每个r长度子集。

如果我缺乏对nPr的描述，这里有一个非常简单的例子来说明我想要做什么：

鉴于设置...

A， B， C

...我想找到每一个两个字符的排列，像这样：

A B
A C
B C

这个例子过于简单化了，因为我真正想要推导的是一个广义的解决方案，它将一个集合（数组）和每个排列中应该包含的项目数作为调用参数。

嗯…现在我已经把这些都写出来了，我觉得我只需要知道如何从集合n中导出长度为r的所有子集，因为我可以使用堆来找到这些子集的排列。

仅供参考:我今年就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