以下内容是基于我对您的帖子的误读。我会留下来娱乐你。真正的解决方案在帖子的末尾。
您确定要从 700 个对象的池中计算 5 个单词的所有可能性吗？
这是我的课程来解决这个问题：
public class SO3206795 {
private static long ct;
private static List<String[]> allPossibleWords(final Set<String> words, final String[] chain) {
final List<String> usedWords = Arrays.asList(chain);
final int offset = usedWords.lastIndexOf(null);
List<String[]> wordsList;
if (offset < 0) {
wordsList = Collections.singletonList(chain);
logCreated();
} else {
wordsList = new ArrayList<String[]>();
for (final String word : words) {
final String[] copy = Arrays.copyOf(chain, chain.length);
if (!usedWords.contains(word)) {
copy[offset] = word;
wordsList.addAll(allPossibleWords(words, copy));
}
}
}
return wordsList;
}
private static List<String[]> getChains(final Set<String> words, final int length) {
final List<String[]> tmpChain = new ArrayList<String[]>();
final String[] chain = new String[length];
tmpChain.addAll(allPossibleWords(words, chain));
return tmpChain;
}
private static Set<String> getWords(final int count, final int letters) {
final Set<String> set = new TreeSet<String>();
final int[] arr = new int[letters];
int tempCt = 0;
while (tempCt++ < count) {
set.add(nextWord(arr));
for (int i = letters - 1; i >= 0; i--) {
if (arr[i] == 25) {
arr[i] = 0;
} else {
arr[i] = arr[i] + 1;
break;
}
}
}
return set;
}
private static void logCreated(){
if(++ct%10000==0){
System.out.println("Created "+ct+" chains");
}
}
public static void main(final String[] args) {
String[]usedArgs=args;
if(args.length==1&&args[0].matches(".*\\D.*")){
usedArgs=args[0].split("\\D+");
};
final int[] values = {10,3,5};
for (int i = 0; i < usedArgs.length&&i<values.length; i++) {
values[i] = Integer.parseInt( usedArgs[i]);
}
final SO3206795 thing = new SO3206795(values[0],values[1],values[2]);
for (final String[] chain : thing.chains) {
System.out.println(Arrays.toString(chain));
}
}
private static String nextWord(final int[] arr) {
final char[] ch = new char[arr.length];
for (int i = 0; i < arr.length; i++) {
final int j = arr[i];
ch[i] = (char) (65 + j);
}
return new String(ch);
}
private static void printInfo(final int numberOfWords, final int wordLength, final int chainLength) {
BigInteger words = BigInteger.valueOf(numberOfWords);
for(int i = 1; i < chainLength; i++){
words=words.multiply(BigInteger.valueOf(numberOfWords-i));
}
System.out.println(MessageFormat.format(
"Creating {0} words of length {1}.\nCreating all possible chains of {2} words.\nThat''s {3} chains in total",
numberOfWords, wordLength, chainLength, words.toString()));
}
Set<String> words;
List<String[]> chains;
public SO3206795(final int numberOfWords, final int wordLength, final int chainLength) {
printInfo(numberOfWords,wordLength, chainLength);
this.words = getWords(numberOfWords, wordLength);
this.chains = getChains(this.words, chainLength);
}
}
它有一个 main 方法，您可以使用最多三个参数调用它：
- numberOfWords（将生成的单词数，默认：10）
- wordLength（字长，默认：3）
- chainLength（字链长度，默认：5）
但是，当我使用值 700、3、5 启动它时，调试输出是这样的：
Creating 700 words of length 3.
Creating all possible chains of 5 words.
That's 165680980516800 chains in total
这是相当多的，你不会这么说吗？这就是 700 * 699 * 698 * 697 * 696 的总和。现在，如果您使用自己的对象而不是字符串，假设您的对象每个大小只有 3 个字节，这意味着您将消耗
497042941550400 Bytes or
485393497607 KB or
474017087 MB or
462907 GB or
452 TB
我不了解您，但是恐怕这比我的机器的 RAM 多得多，而且不幸的是，您的对象不太可能每个只有 3 个字节（并且创建的列表和数组也需要一些重要的内存）。所以我不认为计算所有可能性是一个好主意，即使编码很有趣。
而且也需要很长时间。在我的机器上，创建 10000 个链大约需要 16 毫秒。因此，对于 165680980516800 条链，总持续时间为
2650895688268 ms or
2650895688 sec or
44181594 min or
736359 hours or
30681 days or
84 years
这可能不会太长，因为Deep Thought 花了 7.5 万年才得出答案 42，但它可能仍然比你愿意等待的时间更长。
请：我的数学很糟糕，如果有人向我解释为什么这都是胡说八道，我会非常高兴，但我担心我的数字计算正确。
误会结束：
该死，我错过了字母链接约束。这是我更新的解决方案。将上面的 allPossibleWords 方法替换为这两种方法：
private static List<String[]> allPossibleWords(final Set<String> words, final String[] chain) {
final List<String> usedWords = Arrays.asList(chain);
final int offset = usedWords.lastIndexOf(null);
List<String[]> wordsList;
if (offset < 0) {
wordsList = Collections.singletonList(chain);
logCreated();
} else {
wordsList = new ArrayList<String[]>();
for (final String word : words) {
if (!usedWords.contains(word)&&(offset==chain.length-1||isLegalNeighbor(word,usedWords.get(offset+1)))) {
final String[] copy = Arrays.copyOf(chain, chain.length);
copy[offset] = word;
wordsList.addAll(allPossibleWords(words, copy));
}
}
}
return wordsList;
}
private static boolean isLegalNeighbor(final String left, final String right) {
return left.charAt(left.length()-1)==right.charAt(0);
}
此外，我们将用更随机的版本替换 getWords
private static Set<String> getWords(final int numberOfWords, final int wordLength) {
final Set<String> set=new TreeSet<String>();
final Random r = new Random();
while(set.size()<numberOfWords){
final char[] ch = new char[wordLength];
for (int i = 0; i < ch.length; i++) {
ch[i]=(char) (65+r.nextInt(26));
}
set.add(new String(ch));
}
return set;
}
现在我实际上得到了 200 个单词的合理执行时间，但是 700 个单词仍然会在看起来永远存在之后创建 OutOfMemoryError。
无论如何，这是pastebin 的完整解决方案。
这是修正后的数学：
大约有 362559479 种可能的组合
700 * (699/26) * (698/26) * (697/26) * (696/26)
给定一个 3 字节的对象大小，这意味着内存消耗
1087678437 Bytes or
1062185 KB or
1037 MB or
1 GB
在我的机器上，创建 10000 个带有字母链接的链大约需要 500 毫秒。因此，对于 362559479 条链，总持续时间为
181279739 ms or
181279 sec or
3021 min or
50 hours or
2 days
这些仍然是令人印象深刻的数字，我想说