栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

获取字符串或组合的所有可能排列,包括Java中的重复字符

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

获取字符串或组合的所有可能排列,包括Java中的重复字符

您将必须对要获得的功能进行更具体的说明。“组合”有许多不同的定义,您还没有指定要组合还是无序。

从数学上讲,如果您有n个元素并希望列出k个元素(按重复顺序排列),则可以

n ^ k

组合。(在您的原始示例中,6 ^ 4 = 1296个组合,很多!)。但是,如果您有n个元素,并且想要一个k个元素的MULTISET(无序重复),那么您可以

(n + k - 1)! / (k! * (n - 1)!)

组合,并且很难枚举。

如果k很小,则可以生成数量有限的for循环的第一个,但是随着k的增加,这很快变得很麻烦。这强烈暗示需要使用RECURSIVE方法:

public static String[] getAllLists(String[] elements, int lengthOfList){    //initialize our returned list with the number of elements calculated above    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];    //lists of length 1 are just the original elements    if(lengthOfList == 1) return elements;     else    {        //the recursion--get all lists of length 3, length 2, all the way up to 1        String[] allSublists = getAllLists(elements, lengthOfList - 1);        //append the sublists to each element        int arrayIndex = 0;        for(int i = 0; i < elements.length; i++)        { for(int j = 0; j < allSublists.length; j++) {     //add the newly appended combination to the list     allLists[arrayIndex] = elements[i] + allSublists[j];     arrayIndex++; }        }        return allLists;    }}

此方法不仅会生成所有列表,还将按顺序枚举它们。也就是说,输出将是

aaaaaaabaaacaaa1aaa2aaa3aabaaabbaabcaab1...3323333a333b333c333133323333

使用原始输入。它也可以生成任何长度的单词(对此请务必小心!仅使用长度为8的单词,我就总结了1,679,616个组合!)。

如果该方法使您感到困惑(这是递归方法,那么很难遵循),或者如果您想解决第二个组合问题,请随时提出。另外,此方法效率不高,因为它会重新计算所有子列表的组合,因此对于真正的长列表而言,它是不可行的。如果您确实想要效率,可以将已经计算出的元组存储在全局列表中。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/367343.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号