0

我想创建一个包含一系列 4 个字母的所有排列的数组（将它们称为 A、C、G、T 以表示 4 种核苷酸碱基）。程序应该询问用户 k 的值，即排列的长度。我已经让它工作到可以得到排列的地步，但它只显示没有重复的排列。这是程序，它现在给我的输出，以及我希望它给我的输出。

import java.util.Arrays;
import TerminalIO.*;
public class Permute {
    static KeyboardReader reader= new KeyboardReader ();
    static int k= reader.readInt("Enter k-tuple");
    static void permute(int level, String permuted,
                        boolean[] used, String original) {

        if (level == k) {
            System.out.println(permuted);
        } else {
            for (int i = 0; i < 4; i++) {
                if (!used[i]) {
                    used[i] = true;
                    permute(level + 1, permuted + original.charAt(i), used, original);
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        String s = "ACGTACGTACGTACGTACGT";
        boolean used[] = new boolean[20];
        Arrays.fill(used, false);
        permute(0, "", used, s);
    }   
}

当我输入 K 值 2 时，它给了我：

  • 交流电
  • 股份公司
  • 在
  • 加州
  • CG
  • 电脑断层扫描
  • 遗传算法
  • GC
  • 燃气轮机
  • 助教
  • TC
  • TG

理想情况下，它将打印：

  • 交流电
  • 股份公司
  • 在
  • AA
  • 加州
  • 抄送
  • CG
  • 电脑断层扫描
  • 遗传算法
  • GG
  • GC
  • 燃气轮机
  • 助教
  • TC
  • TG
  • TT
4

3 回答 3

1 
public class Permute {

    static String s = "ACGT";

    static void permute(int level, String prefix) {

        if (level == 0) {
            System.out.println(prefix);
            return;
        }
        for (int i = 0; i < s.length(); i++)
            permute(level - 1, prefix + s.charAt(i));
    }

    public static void main(String[] args) {
        int k = 4;
        permute(k, "");
    }   

}
于 2013-06-25T18:57:27.503 回答
1 
ArrayList<ArrayList<String>> results= new ArrayList<ArrayList<String>>();

public static void main(String... args) {
    String[] letters= new String[] {"a", "t", "g", "c"};
    List<String> list= Arrays.asList(letters);

    for (int i=0; i<list.size(); i++) {
        ArrayList<String> startList= new ArrayList<String>();
        startList.add(list.get(i));
        permute(list, 2, startList);
    }

    //result lists of strings are saved in results
    for (ArrayList<String> result : results) {
        System.out.println(result);
    }
}

private static void permute(List<String> letters, int endLength, List<String> startList) {
    if (startList.size() >= endLength) {
        results.add(startList);
        return;
    }

    for (int i=0; i<letters.size(); i++) {
        ArrayList<String> newStartList= new ArrayList<String>(startList);
        newStartList.add(letters.get(i));
        permute(letters, 2, newStartList);
    }
}
于 2013-06-25T19:04:06.520 回答
1

那这个呢？（没有递归）

void permute(char[] alphabet, int k) {
    int permutationNumber = (int) Math.pow(alphabet.length, k);
    for (int i = 0; i < permutationNumber; i++) {
       for (int j = 0; j < k; j++) {
          System.out.print(alphabet[(i + (j * i / alphabet.length)) % alphabet.length]);
       }
       System.out.println();
    }
 }
于 2013-06-25T19:20:46.573 回答