解决nPr(排列)的算法.对于假人 [英] Algorithm to solve nPr (permutations). For dummies

问题描述

是的，我有RTFM.或者，在这种情况下，是RTFSO.如果它出现在"npr"或排列"的搜索结果中，我会阅读.而且，虽然我已经实现了Heap的算法，但是我无法从那里(所有排列)到nPr(长度为r的所有排列，从较大的集合n中移出)实现飞跃.

Yes, I've RTFM. Or, in this case, RTFSO. If it showed up in the search results for "npr" or "permutation", I read it. And while I have implemented Heap's algorithm, I can't make the leap from there (all permutations), to nPr (all permutations of length r, out of a larger set n).

在不包含实际代码的冗长解释中，首选实际算法(伪代码很好).如果您想学习该理论，那很好，我很乐于从中学习，但我也希望随附的代码.如果您可以说堆的话，那就太好了；否则，我会弄混.

An actual algorithm (pseudo-code is fine) is preferred to a long-winded explanation that doesn't include actual code. If you want to school me on the theory, fine, I'll be happy to learn from it, but I'd also like the accompanying code. If you can put in terms of Heap's, great; otherwise, I'll muddle through.

我没有任何代码可以显示给您(除非您想在VBScript中实现Heap的实现(这是我在工作中要做的全部工作))，因为正如我所说，我不知道去哪里从那里得到集合n的每个r长度子集.

I don't have any code to show you (unless you want to see Heap's implemented in VBScript (which is all I have to work with at work)) because, as I said, I don't know where to go from there to get every r-length subset of set n.

如果缺少我对nPr的描述，这是我要执行的操作的一个非常简单的示例:

In case my description of nPr is lacking, here is a very simple example of what I'm looking to do:

给出设置...

A，B，C

...我想查找每个两个字符的排列，如下所示:

...I want to find every two-character permutation, like so:

A B
A C
B C

A B
A C
B C

该示例过于简单，因为我真正想得出的是一个通用的解决方案，该解决方案采用一个集合(数组)以及每个排列中应包含的项数作为调用参数.

That example is overly simplistic, as what I am really trying to derive is a generalized solution that takes a set (array), and the number of items that should be in each permutation, as calling parameters.

嗯...现在我已经把所有这些写完了，在我看来，我真的只需要知道如何从集合n中得出长度为r的所有子集，因为我可以找到这些子集的置换使用堆的.

Hmmm...now that I've written all this out, it seems to me that I only really need to know how to derive all subsets of length r from set n, since I can then find the permutations of those subsets using Heap's.

仅供参考:今年我将满50岁；这不是功课.

FYI: I'll be 50 this year; this isn't homework.

推荐答案

相对简单的递归:

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

在JavaScript中:

In 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

这篇关于解决nPr(排列)的算法.对于假人的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！