子序列枚举

梦里梦外; 2022-05-22 08:54 158阅读 0赞

这个可以是自己无聊点出来的，键盘输入流输入 一个字符串然后，给出所有子序列的集合，包括空和自己。虽然无用，但胜过于无。因为用了Math的随机数，时间成本可能会有点高。。。。。。。

import java.util.*;
    
    /**
     * 子序列枚举
     * @Author Peter_S
     * @Date 2018/6/8
     */
    public class Sequence {
        /**
         * 枚举
         */
        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            String str1 = input.next();
            System.out.println(str1);
            System.out.println(subsequence(str1));
    
        }
    
        /**
         * 给出str的所有子序列
         * @param str
         * @return
         */
        public static List<String> subsequence(String str){
            List<List<Integer>> subscripts = subscript(str.length());
            List<String> subsequences = new ArrayList<>();//所有子序列集合
            for (int i = 0;i<subscripts.size();i++){
                List<Integer> sub = subscripts.get(i);
                String s = "";
                for (int j = 0;j<sub.size();j++){
                    s = s+str.charAt(sub.get(j));
                }
                subsequences.add(s);
    
            }
            return subsequences;
        }
    
        /**
         *
         * @param length 长字符串长度
         * @return
         */
        public static List<List<Integer>> subscript(int length){
            List<List<Integer>> ret = new ArrayList<>();
            List<Integer> numbers = collections(length);
            ret.add(new ArrayList<>());
            for (int i = 1;i<=length;i++){
      //i 子序列长度
                int j = numbers.get(i-1); //j 子序列长度对应的个数
                for (int x = 0;x < j;){
                    List<Integer> subscript = new ArrayList<>();
                    while (subscript.size()<i){
                        int num = (int)(Math.random()*length);
                        if (!subscript.contains(num)){
                            subscript.add(num);
                        }
                    }
                    subscript.sort(Integer::compareTo);
                    if (!ret.contains(subscript)){
                        ret.add(subscript);
                        x++;
                    }
                }
            }
            return ret;
        }
    
        /**
         * 参考集合与子集的关系，返回List集合 是子序列长度1，2.。。。多对应的个数
         * @param length 字符串长度
         * @return
         */
        public static List<Integer> collections(int length){
            List<Integer> numbers = new ArrayList<>();
            for (int i = 1;i<=length;i++){
                numbers.add(combination(i,length));
            }
            return numbers;
        }
    
        /**
         * 求组合数  (n!)/[m!*(n-m)!]
         * @param m 上标
         * @param n 下标
         * @return
         */
        public static Integer combination(int m,int n){
            int i = multiplication(n)/(multiplication(m)*multiplication(n-m));
            return i;
    
        }
    
        /**
         * n的阶乘
         * @param n
         * @return
         */
        public static Integer multiplication(int n){
            int i = 1;
            for (;n>0;n--){
                i = i*n;
            }
            return i;
        }
    }

我自己测试结果如下：：

![70][]

[70]: /images/20220522/bcbc0371b7b54970a9c4c29646266957.png