修改此代码以仅采用一个参数(字符组合的长度)

Question

我正在尝试修改[这里]中答案2中的java代码在字符串中生成字符组合并不完全有效，为什么？ 有一个方法可以完成整个工作并只接受一个参数，即组合中的字符数（即在 main 中称为 method（int））。

这实际上是一个家庭作业，编写一个与上面链接中的代码相同的递归代码，即打印所需长度的所有字符组合，但在这种情况下，从一组固定的字符 A、C、G 和 T（例如，如果调用 method（2），它会打印 AA、AC、AG、AT、CA、CC...）。

到目前为止，我只得到：

public static void printAllDNAs(int n) {
    String[] dna;
    dna = new String[4];
    dna[0] = "A";
    dna[1] = "C";
    dna[2] = "G";
    dna[3] = "T";
    String prfx = "";
    if (n == 0) {
        System.out.println(prfx);
    } else {
        for (int i = 0; i < dna.length; i++) {
            System.out.print(prfx + dna[i]);
            printAllDNAs(n - 1);
        }
    }
}
public static void main(String[] args) {
    printAllDNAs(3);
}
}

这显然根本不对。我知道我需要依次给 prfx 集合中每个字母的值，并将集合中的一个或多个字符附加到其中。有人可以给我一两个提示，我应该走哪条路吗？非常感谢。

Answer 1

您可以尝试以下解决方案：

public static void printDNARecursive(ArrayList<String> dnaCombinations, String prefix, String[] dnaArray, int depth) {
    if (prefix.length() == depth || dnaArray.length == 0) {
        return;
    }
    for (int i = 0; i < dnaArray.length; i++) {
        String dna = dnaArray[i];
        if (dna == null) {
            continue;
        }
        dnaCombinations.add(prefix + dna);
        String[] copyOf = Arrays.copyOf(dnaArray, dnaArray.length);
        copyOf[i] = null;
        printDNARecursive(dnaCombinations, prefix + dna, copyOf, depth);
    }
}

它是如何工作的 - 这个代码使用而不是打印DNA来筛选它，将它们保存在变量dnaCombinations。如果你的DNA达到最大深度的长度（depth变量），那么它就不会走得更远。

它与你的有点不同，因为在dnaCombinations里面你也会有"A", "C", "G", "T"但然后你可以从dnaCombinations唯一的字符串打印，长度由你选择。

这里有一个小例子它是如何工作的：

public static void main(String... args) {
    String[] dna = new String[] { "A", "C", "G", "T"};
    ArrayList<String> result = new ArrayList<String>();
    printDNARecursive(result, "", dna, 2);
    for (String d : result) {
        System.out.println(d);
    }
}

结果是：A AC AG AT C CA CG CT G GA GC GT T TA TC TG

随意添加任何修改或将其用作模板

Answer 2

String prfx需要在函数之外。用char[]代替它也会让事情变得更容易、更快。请参阅下面的解决方案。

如果你只需要一个函数：

private static char arr[];
private static final char[] dna = "ACGT".toCharArray();
public static void printAllDNAs(int n)
{
   if (arr == null)
      arr = new char[n];
   if (n == 0)
   {
      System.out.println(String.valueOf(arr));
      return;
   }
   for (char c: dna)
   {
      arr[n-1] = c;
      printAllDNAs(n-1);
   }
   if (n == arr.length)
      arr = null;
}

如果您不介意多个功能，这可能会更好（+稍微快一点）：

public static void printAllDNAs(int n)
{
  arr = new char[n];
  printAllDNAsInternal(n);
}
private static void printAllDNAsInternal(int n)
{
   if (n == 0)
   {
      System.out.println(String.valueOf(arr));
      return;
   }
   for (char c: dna)
   {
      arr[n-1] = c;
      printAllDNAs(n-1);
   }
}