バックグラウンド
私と他の数人は、大学のプロジェクトで Android アラーム アプリケーションを開発しています。「チャレンジ」と呼ばれる概念があり、ユーザーはアラームを閉じるために 1 つを完了する必要があります。これらの課題/ユーザー ストーリーの 1 つは、数値のリストを ASC/DESC で正しく並べ替えることです。
問題
目標/問題は、ユーザーに最大の混乱をもたらすリストを提供することです。これにより、人間にとってリストをソートするのができるだけ難しくなります。
私の基本的な考え方は、例えば [131, 129, 315, 328, 931, 953] のようなシャッフルされた数字のリストを取得した場合、それを並べ替えるのは難しいということです (混乱のより良いアイデアがある場合は、共有してください)。
ここでの主な関心事はコンピューティング パフォーマンスではなく、リストの品質です。
解決の試み
最初に、すぐにフィッシャー・イェーツ、シャッフルを検索し、次に分散と標準偏差に関する情報を探しました。
私の友人の 1 人は、(ステップ 1) 100 から 999 までの 3 つの数字を生成し、(ステップ 2) 小さい数字を 3 つ生成すると (大きな数字のそれぞれに対して 1 と言い、大きな数字に加算すると、素敵で紛らわしい数のリスト. そしておそらく, いくつかのチェックを入れて, 大きい数が十分に変化していることを確認し, 小さいものがあまり変化していないことを確認します. そして最後に, 計算された数のシャッフルを行います.
私が思いついた最高のもの（Javaで書かれていますが、どの言語でも問題ありません）は次のとおりです。
// Config variables.
int min = 101;
int max = 999;
int innerMin = 1;
int innerMax = 99;
int innerSize = 3;
int outerSize = 3;
// The numbers here were just picked "at random".
double minVariance = 100.0;
double maxInnerVariance = 33.0;
// java.util.Random is maybe not optimal, but for now...
Random rng = new Random();
int[] numbers = new int[outerSize * innerSize];
// Fill big array first.
int[] big = new int[outerSize];
while ( computeVariance( big ) < minVariance ) {
for ( int i = 0; i < outerSize; ++i ) {
int random;
do {
// Maybe use nextGaussian here instead?
random = (int) (min + (rng.nextDouble() * (max - min)));
} while ( random % 10 == 0 ); // Exclude all numbers that are modulo 10, too easy.
big[i] = random;
}
}
for ( int i = 0; i < outerSize; ++i ) {
// Fill a small array for each big array.
int[] small = new int[innerSize];
while ( computeVariance( small ) > maxInnerVariance ) {
for ( int j = 0; i < innerSize; ++i ) {
int random;
do {
// Maybe use nextGaussian here instead?
random = (int) (innerMin + (rng.nextDouble() * (innerMax - innerMin)));
} while ( random % 10 == 0 ); // Exclude all numbers that are modulo 10, too easy.
small[i] = big[i] + random;
numbers[innerSize * i + j] = small[i];
}
}
}
// Finally shuffle.
fisherYatesShuffle( numbers, rng );
ご覧のとおり、コードは非常に複雑で、ネストされた 4 つのループがあります。これを概念的に、またはアルゴリズム的に行うなど、より良い方法はありますか?
編集
編集1、@ElKamina :sコメントの後にいくつかの仮定をより明確にしました...
私は次の視覚的な仮定を立てました: - 数字のリストは視覚的にシャッフルされます。- 数字をさらに混乱させるために、背景色を数字に提供するために再びシャッフルされます。-あなたが提起した認知の問題に対処するために、数字はグリッドで表されるため、適用されません。
モデルの仮定: - すべての数字は 3 桁です (長さの違いはありません)。
ワーキングソリューション
実装全体をやり直し、nextGaussian などを使用して動作するようにしました。このソリューションは、すべてのクラスターで一意性を保証し (AFAIK)、遅くなる可能性がありますが、ここでは堅牢で品質 > 速度です (コードの最適化は大歓迎です)。
2.0 の標準偏差を使用すると、私が感じるように良好で良好なスプレッドが得られます。より多くのコード @ http://pastebin.com/iu3U6VG0
@Override
public int[] generateList( Random rng, int size ) {
// outer = index 0, inner = index 1.
int[] sizes = computeSizes( size );
int[] numbers = new int[sizes[0] * sizes[1]];
int outerMultiplier = com.google.common.math.IntMath.pow( 10, this.numDigits - 1 );
int innerMax = outerMultiplier - 1;
// Fill outer array first.
int[] outer = new int[sizes[0]];
for ( int i = 0; i < sizes[0]; ++i ) {
outer[i] = RandomMath.nextRandomRanged( rng, 1, 9 ) * outerMultiplier;
}
// Fill inner array for each outer array.
for ( int i = 0; i < sizes[0]; ++i ) {
// Calculate bounds [min, max].
int[] innerBounds = new int[] { RandomMath.nextRandomNon10( rng, 1, innerMax ), RandomMath.nextRandomNon10( rng, 1, innerMax ) };
int diff = innerBounds[1] - innerBounds[0];
if ( diff < 0 ) {
// Wrong order, swap!
PrimitiveArrays.swap( innerBounds, 0, 1 );
diff = -diff;
}
if ( diff < sizes[1] ) {
// Difference is too small, make sure we got room!
innerBounds[0] = Math.max( 1, innerBounds[0] - sizes[1] );
innerBounds[1] = innerBounds[0] + sizes[1];
diff = innerBounds[1] - innerBounds[0];
}
BitSet bits = new BitSet( diff );
boolean filledModulo10 = false;
// Now do the filling.
int[] inner = new int[sizes[1]];
for ( int j = 0; j < sizes[1]; ++j ) {
inner[j] = RandomMath.nextGaussianNon10( rng, innerBounds[0], innerBounds[1], MAX_GAUSS_ITERATIONS, INNER_STANDARD_DEVIATIONS );
// Protect against same numbers all the time, can we do away with this loop? not O(n) but still...
boolean hasDuplicate = false;
for ( int k = 0; k < j; ++k ) {
if ( inner[k] == inner[j] ) {
hasDuplicate = true;
}
}
if ( hasDuplicate ) {
if ( !filledModulo10 ) {
// Set all numbers that end with 0 in BitSet, we don't want them!
// This assumes that neither innerBounds[0, 1] are modulo 10.
for ( int l = ((innerBounds[0] / 10) + 1) * 10; l <= innerBounds[1]; l += 10 ) {
bits.set( l - innerBounds[0] );
}
filledModulo10 = true;
}
// Find first false bit.
// This beats the idea of randomness, but avoiding duplicates is more important!
inner[j] = bits.nextClearBit( 0 ) + innerBounds[0];
}
bits.set( inner[j] - innerBounds[0] );
numbers[sizes[1] * i + j] = outer[i] + inner[j];
}
}
return numbers;
}