以下は、あなたの投稿を読み間違えたことに基づいています。私はあなたを楽しませるためにそれを残します。本当の解決策は記事の最後にあります。
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);
}
}
これには、最大 3 つの引数で呼び出すことができる 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 よりもはるかに多くの RAM が搭載されています。残念ながら、オブジェクトがそれぞれ 3 バイトしかない可能性はほとんどありません (また、作成されたリストと配列にもかなりのメモリが必要です)。だから、コーディングが楽しかったとしても、すべての可能性を計算するのは良い考えではないと思います。
また、それには長い時間がかかります。私のマシンでは、10000 チェーンを作成するのに約 16 ミリ秒かかります。したがって、165680980516800 チェーンの場合、合計持続時間は
2650895688268 ms or
2650895688 sec or
44181594 min or
736359 hours or
30681 days or
84 years
ディープ ソートが答え 42 を導き出すのに 750 万年かかったので、おそらくそれほど長くはありませんが、おそらくあなたが待つよりも長いでしょう。
お願い: 私の数学はひどいものです.なぜこれがすべてナンセンスなのか誰かが私に説明してくれたら、私はもっとうれしいです.
誤解の終わり:
くそー、私は文字リンクの制約を逃しました。これが私の更新されたソリューションです。上記のメソッド allPossibleWords を次の 2 つのメソッドに置き換えます。
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
これらはまだ印象的な数字だと思います