我的排列代码每次都打印 nPn 吗？

Question

所以我正在尝试编写一个代码，它将按照 nPr 方式打印出字符串的所有排列，其中 n 是字符串长度，r 是输入。它接受一个前缀和字符串，以及一个整数。它这样做除了它每次打印 nPn 排列而不是 nPr 排列。

public static void main(String[] args){
    String x = "abcd";
    permu("", x, 2);
}
public static void permu(String pre, String x, int r){
    if(x.length() == 0)
        System.out.println(pre.substring(0, r));
    else{
        for(int i = 0; i < x.length(); i++)
            permu(pre + x.charAt(i), x.substring(0, i) + x.substring(i + 1, x.length()), r);
    }
}

对于 r = 2，我希望它打印 ab、ac、ad、ba、bc、bd、ca、cb、cd、da、db、dc。但它会打印两倍的内容。

Answer 1

您必须将递归限制设置为 r（现在是 n）。大概是这样：

   if(x.length() == 0)
 change to
   if(pre.length() == r)

Answer 2

结果不会让您感到惊讶：您的代码决定了所有 24 种排列。它仅在打印时强制执行最大长度。你可以看出这一点，因为 r 除了打印之外没有在任何地方使用。

如果打印整个字符串，结果为：

abcd
abdc
acbd
acdb
....

您只能看到本质上是完整排列的前几个字符。

如果您想从 4 个中真正挑选 2 个，您应该在挑选 r 项后停止递归：

if (pre.length() == r)
    System.out.println(pre.substring(0, r));

您可能想确保代码在有人使用大于字符串长度的 r 调用它时仍然有效：

if (pre.length() == r || x.length() == 0)
    System.out.println(pre.substring(0, r));

我的排列代码每次都打印 nPn 吗？

My permutation code prints nPn every time?

string

algorithm

double

recursion

permutation