我想生成所有长度为n的字符串，包含字母a,b和c。我得到这个错误java.lang.OutOfMemoryError: Java堆空间。我的堆大小是512m。
当前正在计算的字符串数
3^30 = 205 891 132 094 649
这是相当多…
知道每个String包含三个字节:
3^30 * 3 = 617 673 396 283 947
加上二维数组的32位或64位指针。
3^30 * (3 + 4) = 1 441 237 924 662 540 // 32-bit Java VM
3^30 * (3 + 8) = 2 264 802 453 041 140 // 64-bit Java VM
2 109 261 GB = 2059 TB // 64-bit JVM
我想这就是问题所在。
在500mb的限制下，你可以解这个方程:
3^x * (3 + 8) = 524 288 000
3^x = 47662545
x = log(47662545) / log(3)
x = 7 / 0.477121254719662
x = 14.67
所以，如果我没有忘记的话，你的测试应该对n <= 14有效。当然，除非您删除以下代码，否则它将无法工作:
List<String> result = new ArrayList<String>();
for (char[] permutation : table) {
result.add(new String(permutation));
}
这段代码复制了所有的数据!这意味着你需要两倍的内存。试着马上打印出来
不包含子字符串"ABC"的计数字符串可以用动态规划来解决。
首先，将所有长度为n的字符串的个数命名为S(n)。注意，S(n)很容易计算。S(n) = pow(size_of_the_alphabet,n)
我们将包含ABC的长度为n的字符串的个数命名为A(n)，将首次出现ABC的字符串的个数命名为A(n,k)
现在注意:A(n,k) = (S(k-1) - A(k-1)) * S(n - k - 3)(因为k是第一个出现"ABC"的位置，所以每个字符串都有一个在该位置之前不含"ABC"的子字符串，以及在第一个"ABC"之后的子字符串)
注意A(n) = sum A(n,k) for k in [0..n-3]
现在我们可以计算A(n)从0开始计算A(n)的每个值。
基本大小写很简单，如A(n) = 0 for n = 0,1,2
A(3) = (S(0) - A(0))*S(0) = 1(即"ABC")
等。
一旦你有了A(n)，你可以使用公式S(n) - A(n)得到你正在寻找的数字。
Pseudojava伪代码:
public class Counter {
public int count(int aSize, int n) {
long[] a = new long[n+1]; // n + 1 elements since a[i] contains # of strings containing "ABC"
a[0] = 0;
a[1] = 0;
a[2] = 0;
for (int i = 3; i <= n; ++i){
long sum = 0;
for (int k = 0; k <= i-3; ++k) {
sum += (pow(aSize, k) - a[k]) * pow(aSize, i - k - 3);
}
a[i] = sum;
}
return a[n];
}
public static void main(String... args) {
int aSize = 3; //size of the alphabet
int n = 30; // length of the strings
//final result
long result = pow(aSize, n) - count(aSize, n);
}
}
运行时间为O(n^2)，假设pow为0(1)。如果不是，那么你可以节省一些时间来预先计算S(i)。
空间要求为O(n)。
请注意，这将计算长度== n的所有字符串的数量。如果您想要长度<= n，那么修改是显而易见的(您只需将a中的所有元素相加)。
我注意到你在评论中有一个不同的问题。你想找到所有长度为30,a-z不包含a-c的字符串。这是所有长度为30的d-z字符串的计数。计数是(26-3)^30。
System.out.printf("%,d%n", BigInteger.valueOf(26-3).pow(30));
打印
71,094,348,791,151,363,024,389,554,286,420,996,798,449
您可以将所有可能的字符串编码为数字，而不是记住每个字符串。在您的情况下，您可以使用long .
public static void main(String... args) {
String letters = "abc";
int len = 30;
long combinations = (long) Math.pow(letters.length(), len);
System.out.printf("There are %,d strings%n", combinations);
for (long i = 0; i < 10; i++)
System.out.println(fromLong(i, letters, len));
System.out.println("... some numbers skipped ...");
for (long i = combinations-10; i < combinations; i++)
System.out.println(fromLong(i, letters, len));
}
public static String fromLong(long n, String letters, int len) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(letters.charAt((int) (n % letters.length())));
n /= letters.length();
}
return sb.reverse().toString();
}
打印
There are 205,891,132,094,649 strings
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaac
aaaaaaaaaaaaaaaaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaaaaaaaaaaaaaabb
aaaaaaaaaaaaaaaaaaaaaaaaaaaabc
aaaaaaaaaaaaaaaaaaaaaaaaaaaaca
aaaaaaaaaaaaaaaaaaaaaaaaaaaacb
aaaaaaaaaaaaaaaaaaaaaaaaaaaacc
aaaaaaaaaaaaaaaaaaaaaaaaaaabaa
... some numbers skipped ...
cccccccccccccccccccccccccccbcc
ccccccccccccccccccccccccccccaa
ccccccccccccccccccccccccccccab
ccccccccccccccccccccccccccccac
ccccccccccccccccccccccccccccba
ccccccccccccccccccccccccccccbb
ccccccccccccccccccccccccccccbc
ccccccccccccccccccccccccccccca
cccccccccccccccccccccccccccccb
cccccccccccccccccccccccccccccc
这可以打印从0到3^30-1的所有可能的字符串。您不需要存储所有的编码值，因为您知道所有可能的值都在一个连续的范围内。
您正在尝试计算字符串还是计数字符串?
编辑:我从后面的评论中看到，你知道你在谈论多少字符串:
26^n = 26的n次方(假设你只使用小写字母从'a'到'z')。如果你真的想枚举每个字符串，我强烈建议你不要保留对每个String的引用。如果您最终使用对这些字符串中的每个字符串的悬空引用，那么您将在大约六个字符后耗尽内存。