给定一个长度和一组字符,如何获得所有可能的字符串组合
给定一个长度和一组字符,如何获得所有可能的字符串组合
可能是重复的:
给定长度为n=4
,和一个字符集 -> {'a','b'}
,如何编写一些Java代码来生成包含集合中字符的所有可能长度为n的字符串?
对于上面的例子,结果应该有2^4=16个字符串,即:
aaaa aaab aabb abbb baaa baab babb bbbb bbaa bbab bbba abaa abab abba baba aaba
这是我的代码片段:
public void process(String result, String string) { if(string.length() == 0) { System.out.println(result); }else{ for(int i = 0; i < string.length(); i++) { String newResult = new String(result+string.charAt(i)); String newString = new String(string.substring(0,i) + string.substring(i+1, string.length())); process(newResult, newString); } } }
这似乎只是在做排列,而不是我想要的......
提前谢谢您的帮助 🙂
问题:给定一个长度和一组字符,如何获取所有可能的字符串组合?
原因:作者提到这段代码可能存在错误,但应该可以工作。即使不能工作,也非常接近您所期望的结果。注意,第一个for循环填充了resultList而不是设置值,因为没有要附加的内容。
解决方法:根据代码中的注释,首先根据每个字母的size^(n-1)次方进行复制。然后在每个深度循环中,根据给定的字符列表components,在结果列表results中的每个字符串后追加一个字符,直到达到给定的长度n。
代码如下:
ArrayListresults = new ArrayList (); ArrayList components = new ArrayList (){"a","b","c"}; int n = 4; int size = components.size(); for (int j = 0; j < size; j++) { // start with size^(n-1) copies of each letter. for (int i = 0; i < Math.pow(size, n-1); i++) { results.add(components.get(j)); } } // At this point you have each letter in there once... for (int depth = 1; depth < n; depth++) { for (int j = 0; j < size; j++) { String toAppend = components.get(j); for (int i = j; i < results.size(); i += size) { String current = results.get(i); current += toAppend; results.set(i, current); } } }
需要注意的是,作者更喜欢其他答案,但直到发布这个答案之后才看到它...
给定一个长度和一组字符,如何获取所有可能的字符串组合
这个问题的出现是因为,我们需要找到一种方法来获取给定长度和字符集合的所有可能的字符串组合。解决这个问题的方法是通过计数的方式来枚举从最低元素到最高元素之间的所有“数字”。
我们可以将问题类比为计数。从aaaa计数到bbbb,就像二进制一样。
aaaa -> 0000
aaab -> 0001
aaba -> 0010
aabb -> 0011
...
bbbb -> 1111
对于更高的元素数量,只需将计数视为在更高的进制中进行计数。例如,对于八个元素,集合为{a, b, c, d, e, f, g, h},你将在八进制中进行计数:
aaaa -> 0000
aaab -> 0001
...
aaah -> 0007
aaba -> 0010
...
hhhh -> 7777
通过从0000计数到9999,你可以枚举出所有长度为4的0-9的组合。
感谢你发布了你的代码。你是对的,你在做排列。一个更好的方法是使用多组合(有重复元素的有序组合)算法,就像这里讨论的那样。
我不确定这种二进制可视化是否有助于解决包含超过两个字符的问题。无论如何,这是相同的原理,如果你有n个不同的元素,你就是在以n为基数的进制中编写“数字”。
当然有用,只需将概念扩展到更高的进制,比如八进制对于8个元素。
我更新了答案以澄清更高的进制。
我的评论主要是关于这种可视化(无论基数如何)是否有助于解决问题。但我想这种想法是傲慢的,因为并不是每个人的思维方式都一样!我认为+1票数表明我在少数派 🙂
当然,一切都好 🙂 当我们的老师用数字系统解释组合数学时,我和班上的同学更容易理解,因为我们都知道如何计数。我是一边学习一边教的。虽然为了澄清,可能将另一个进制包含进来是一个好主意,所以谢谢你。
问题的出现原因:
问题是由于代码中存在错误逻辑导致的。在给定长度和一组字符的情况下,代码判断字符串长度为0时打印结果,但实际上应该打印一个消息并退出函数。
解决方法:
修复逻辑错误,将代码改为打印消息并退出函数。
整理成文章如下:
给定一个长度和一组字符,如何获取所有可能的字符串组合?
在解决这个问题的过程中,我们发现了一个逻辑错误。代码中判断字符串长度为0时打印结果,但实际上应该打印一个消息并退出函数。
具体代码如下:
if (string.length() == 0) { System.out.println(result); }
这段代码的问题在于,它判断的是字符串`string`的长度是否为0,然后打印的是结果`result`,而不是字符串本身。这是不正确的。
修复逻辑错误的方法是将代码改为打印一个消息并退出函数。这样可以避免打印空字符串,而是给出一个明确的提示。修正后的代码如下:
if (string.length() == 0) { System.out.println("String is empty. Exiting function."); return; }
通过修复这个逻辑错误,我们可以正确地处理给定长度和一组字符的情况,获取所有可能的字符串组合。