背景
我和其他一些人正在我们大学的一个项目中开发一个 android 警报应用程序。我们有一个名为“挑战”的概念，其中用户必须完成一项才能关闭警报。这些挑战/用户故事之一是正确地对数字列表 ASC/DESC 进行排序。
问题
目标/问题是为用户提供一个提供最大混淆的列表，以便该列表尽可能难以为人类排序。
我的基本想法是，如果你得到一个打乱数字的列表，例如：[131、129、315、328、931、953]，那将很难排序（如果你对混淆有更好的了解，请分享）。
计算性能不是我们主要关心的问题，而是列表的质量。
解决问题的尝试
首先，我立即搜索 Fisher-Yates，改组，然后继续寻找有关方差和标准差的信息。
我的一个朋友建议，如果我们说（第 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;
}