Rosalind Java|Ordering Strings of Varying Length Lexicographically

Rosalind枚举字母的所有组合都是编程问题。
与上一个问题相似：Rosalind Java|Enumerating k-mers Lexicographically
本博客可以在一定程度上借鉴。

Ordering Strings of Varying Length Lexicographically

Problem：
Say that we have strings s=s1s2?sm and t=t1t2?tn with m

1. If s=t′, then we set s
2. Otherwise, s≠t′. We define sLext if s>Lext′ (e.g., APPLET

Given: A permutation of at most 12 symbols defining an ordered alphabet A and a positive integer n (n≤4).
Sample input：

D N A
3

Return: 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.)
Sample output：

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，所有需要输出长度小于等于n的字母的组合，主题也增加了限制，即输出顺序应与字母给出的顺序一致。这就要求我们在组合字母时注意添加顺序。Rosalind根据提供的标准答案，字母组合应逐一枚举。在向前枚举下一个元素之前，将元素添加到上限n。输出顺序也应与枚举顺序一致。

看似很简单的题目，但背后需要深入思考的操作逻辑却很详细！

先分析解题思路：
1.读取所有英文字母(去除间隔空间)和组合长度的上限n。
2.逐一读取英文字母到集合的方法。
3.在方法一内嵌套方法二，给集合中新添元素后继续增加字母库里的元素。
4.LinkedHashSet判断重复元素并删除它们。
5.增强for将输出结果集合到屏幕上。

以下是实现代码：

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循环的思路，这种方式简单易行，不过代码敲得会多一点，有点浪费键盘。而且嵌套for循环还有一个弊端，那就是不能灵活根据组合上限n调整循环次数。如果题目给出的n非常大，那么循环for方法将会非常非常麻烦。

当然本文的代码也可以进行算法优化：所用的两个方法可以合并成为一个递归算法，在这里就不给大家做改进啦（脑细胞已经死伤惨重），有想法的大佬可以上手进行深层修改，欢迎大家随时交流。