序列避免近碰撞
序列避免近碰撞
提问于 2016-07-03 17:51:14
任务
找到在最小和最大之间的所有数字的序列，其中每个数字与序列中的每一个其他数字至少有"d“位数不同。
子序列
实例
对于min = 0，max = 1000和d= 2，以下是一个可能的解决方案序列的一部分：
- 123←好
- 132←良好
- 145←好
- 146←坏
Notes
这有点实际。多年来，我一直认为这是一个不断出现的问题。基本上这是网址缩写/奖品代码/会议室代码/等等的一种模式.
我希望能够从列表中分发代码，并且让每个代码都是:a--输入简单，B--不太可能因为键入错误而意外地与另一段代码发生冲突。
没有理由在10号基地工作。为了清晰起见，我用这种方式表达了这个问题，但在实际情况下，我们也会利用字母。
子-Note
这没那么实际。如果您只使用六个“数字”(允许数字和大写字母)，那么您就有超过20亿种选择。在大多数情况下，这似乎是足够的，除了URL缩短器。尽管如此，我还是在想，能够从这个空间生成一个随机数，并且能够快速地检查它是否至少与所有其他已经分发的数字不同，这将是很好的。生成一个解决方案序列不是完全相同的问题，但它似乎很有趣，我希望有人想出一种聪明的方法来构造数据，以便有效地搜索这些近距离碰撞。
回答 1
Code Golf用户
发布于 2016-07-03 19:09:34
这是一种可怕的，蛮力的方式来产生序列。虽然这里可能有几个简单的收获，但我并没有尝试做太多的事情来加快速度。我试着想出一种方法，至少能使这个速度快几个数量级，而不是找出几个百分点的改进。
public static IEnumerable<int> GetDifferentCodes(int min, int digits, int minDifference)
{
var max = Math.Pow(10, digits) - 1;
var goodCodes = new List<int>();
var goodCodeDigits = new List<short[]>();
for (var i = min; i < max; i++)
{
var newDigits = GetDigits(i, digits);
if (!goodCodeDigits.All(goodCode => HasMinDiff(goodCode, newDigits, digits, minDifference)))
continue;
goodCodes.Add(i);
goodCodeDigits.Add(newDigits);
}
return goodCodes;
}
private static readonly int[] Powers = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
private static short[] GetDigits(int num, int digits)
{
var ret = new short[digits];
for (var i = 0; i < digits; i++)
{
ret[i] = (short) ((num/Powers[i]) % 10);
}
return ret;
}
private static bool HasMinDiff(short[] goodDigits, short[] digitsToCheck, int digits, int minDiff)
{
var difference = 0;
for (var i = 0; i < digits; i++)
{
if (goodDigits[i] == digitsToCheck[i]) continue;
if (++difference >= minDiff) return true;
}
return false;
}页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/84376
复制相关文章
相似问题
腾讯云开发者
