不同长度的排列

Question

可能的重复：
从 n 返回 k 元素的所有组合的算法

我想要做的是生成所有不同长度的 1-9 排列。例如，长度为 1 的所有排列都可以简单地表示为 {1}、{2}、{3}、{4} .. 等等。 长度为 2 的排列为：{1,2}, {1,3}, {1,4} .. 到目前为止，我一直在使用 std::next_permutation() ，但在这种情况下它无法完成这项工作。

有没有什么办法可以不使用递归来解决这个问题呢？如果没有，并且您提供了任何代码，如果您能向我解释，我将非常感激，因为我现在真的很努力解决递归问题，尤其是自己实现递归解决方案。提前致谢。

Answer 1

我将使用的方法从 hakmem 175 开始，即找到具有相同位数的下一个更高的数字。
假设您在一个 int 中编写了 10 个数字（从位 0 到位 9）
这意味着您必须从 1 循环到 10，并用第一个接近您的数字对的数字来填充您的 start int。

例如：对于 {1},{2} ...起始 int 将为 2^0
对于 {1,2} {1,3} ...起始整数将为 2^0+2^1
等等。

之后，您必须创建一个可以解释该数字的方法（检查是否设置了某个位，然后相应的数字将出现在序列中）。

之后调用 hakmems 方法获取下一个数字：

unsigned nexthi(unsigned a) {
  unsigned c = (a & -a);
  unsigned r = a+c;
  return (((r ^ a) >> 2) / c) | r);
}

并继续循环，直到没有数字剩余。

并转到下一个位数 (1->10)

我建议您查看 hakmem 方法以了解它是如何工作的，如果您了解一些有关位的知识，那么实现很容易。

Answer 2

void permute(std::vector<int>& digits, int length) {
    if (length == 0) {
        std::cout << "{";
        for (int i = 0; i < digits.length; i++) {
            std::cout << digits[i] << ",";
        }
        std::cout << "}" << std::endl;
        return;
    }

    for (int i = 0; i < 9; i++) {
        std::vector<int> newDigits(digits);
        newDigits.push_back(i);
        permute(newDigits, length -1);
    }
}

在 main 中将其称为

std::vector<int> digits;
permute(digits, 10); // For 10 digit permutations. 

现在，如果您想获得长度为 1,2 ... n 的排列，那么您所要做的就是将排列函数放入循环中。

请注意，这不是最有效的实现。但我想这应该清楚地说明了递归。