Rosalind枚举字母的所有组合都是编程问题。 与上一个问题相似：Rosalind Java|Enumerating k-mers Lexicographically 本博客可以在一定程度上借鉴。
Ordering Strings of Varying Length Lexicographically
Say that we have strings s=s1s2?sm and t=t1t2?tn with m<n. Consider the substring t′=t[1:m]. We have two cases:
- If s=t′, then we set s<Lext because s is shorter than t (e.g., APPLE<APPLET).
- Otherwise, s≠t′. We define s<Lext if s<Lext′ and define s>Lext if s>Lext′ (e.g., APPLET<LexARTS because APPL<LexARTS).
A permutation of at most 12 symbols defining an ordered alphabet A and a positive integer n (n≤4). ：
D N A 3
All strings of length at most n formed from A, ordered lexicographically. (Note: As in “Enumerating k-mers Lexicographically”, alphabet order is based on the order in which the symbols are given.) ：
D DD DDD DDN DDA DN DND DNN DNA DA DAD DAN DAA N ND NDD NDN NDA NN NND NNN NNA NA NAD NAN NAA A AD ADD ADN ADA AN AND ANN ANA AA AAD AAN AAA
简单总结一下题目大意:给出一系列英文字母和数字n，。这就要求我们在组合字母时注意添加顺序。Rosalind根据提供的标准答案，字母组合应逐一枚举。在向前枚举下一个元素之前，将元素添加到上限n。输出顺序也应与枚举顺序一致。
看似很简单的题目，但背后需要深入思考的操作逻辑却很详细！
先分析解题思路：
public class Ordering_Strings_of_Varying_Length_Lexicographically {
public static void main(String[] args) {
//1.输入组合长度n和待组合字母 Scanner sc = new Scanner(System.in); System.out.println("请输入组合长度n："); int n = sc.nextInt(); Scanner sr = new Scanner(System.in); System.out.println("请输入待组合的字母：");//网站给出的文件有空间间隔，这里输入需要去除空间。 String alphabet = sr.nextLine();
//2.最终输出
kmers(alphabet, n);
}
//1.方法一：遍历库的首字母
public static void kmers(String alphabet, int n) {
//初始默认i为0，意为从第一个字母开始遍历产生kmers
List<String> finalphabet = new ArrayList<>();
for (int j = 0; j < alphabet.length(); j++) {
finalphabet.add(String.valueOf(alphabet.charAt(j)));
//1.1循环遍历
thenAdd(alphabet, finalphabet, n, 0);
}
//1.2集合去重，相当于将ArrayList元素放进LinkedHashSet
Set<String> newfinal = new LinkedHashSet<>(finalphabet);
//1.3集合输出
for (String s : newfinal) {
System.out.println(s);
}
}
//2.方法二：给每一个新添元素后继续增加字母库里的元素
public static void thenAdd(String alphabet, List<String> finalphabet, int n, int i) {
i += 1;
int size = finalphabet.size();
for (int m = 0; m < alphabet.length(); m++) {
//从alphabet库取元素
finalphabet.add(finalphabet.get(size - 1) + alphabet.charAt(m));//从finalalphabet只取最后一个元素进行累加
if (i < n - 1) {
thenAdd(alphabet, finalphabet, n, i);
}
}
}
}
循环嵌套的改进
关于这道题，解法有很多。手勤的朋友也可以采用的思路，这种方式简单易行，不过代码敲得会多一点，有点浪费键盘。而且嵌套for循环还有一个弊端，那就是不能灵活根据组合上限n调整循环次数。如果题目给出的n非常大，那么循环for方法将会非常非常麻烦。
当然本文的代码也可以进行算法优化：，在这里就不给大家做改进啦（脑细胞已经死伤惨重），有想法的大佬可以上手进行深层修改，欢迎大家随时交流。