问序列避免近碰撞
EN

Code Golf用户

提问于 2016-07-03 09:51:14

回答 1查看 120关注 0票数 1

任务

找到在最小和最大之间的所有数字的序列，其中每个数字与序列中的每一个其他数字至少有"d“位数不同。

子序列

实例

对于min = 0，max = 1000和d= 2，以下是一个可能的解决方案序列的一部分：

123←好
132←良好
145←好
146←坏

Notes

这有点实际。多年来，我一直认为这是一个不断出现的问题。基本上这是网址缩写/奖品代码/会议室代码/等等的一种模式.

我希望能够从列表中分发代码，并且让每个代码都是:a--输入简单，B--不太可能因为键入错误而意外地与另一段代码发生冲突。

没有理由在10号基地工作。为了清晰起见，我用这种方式表达了这个问题，但在实际情况下，我们也会利用字母。

子-Note

这没那么实际。如果您只使用六个“数字”(允许数字和大写字母)，那么您就有超过20亿种选择。在大多数情况下，这似乎是足够的，除了URL缩短器。尽管如此，我还是在想，能够从这个空间生成一个随机数，并且能够快速地检查它是否至少与所有其他已经分发的数字不同，这将是很好的。生成一个解决方案序列不是完全相同的问题，但它似乎很有趣，我希望有人想出一种聪明的方法来构造数据，以便有效地搜索这些近距离碰撞。

sequence

number-theory

fastest-algorithm

智慧园区场景解决方案

基于腾讯孪生平台物联网平台能力、视频AI智能分析能力和3D可视化云渲染等产品能力，提供完整的智慧园区方案

回答 1

Code Golf用户

发布于 2016-07-03 11: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;
}