Sequence avoiding near collision

Question

Task

Find a sequence of all numbers between min and max where every number differs from every other number in the sequence by at least "d" digits.

Example of sub-sequence

For min = 0, max = 1000 and d = 2, the following is part of one possible solution sequence:

• 123 ← Good
• 132 ← Good
• 145 ← Good
• 146 ← Bad

Notes

This is a bit practical. I was thinking about this as a problem that has kept cropping up over the years. Basically it's a pattern in URL shorteners / prize codes / conference room codes / etc...

I'd like to be able to hand out codes from a list, and have each code be: A - Simple to type, and B - Be somewhat unlikely to accidentally conflict with another code because of a typing mistake.

There's no reason to work in base ten. I've expressed the problem that way for clarity, but in real cases we'd take advantage of letters as well.

Sub-Note

This is not that practical. If you use just six "digits" (allowing numbers and capital letters), then you have over two billion choices. That seems like plenty for most cases except for the URL shortener. Still I was thinking it would be nice to be able to generate a random number from that space and be able to quickly check that it was at least "d" different from all others that had been handed out up to that point. Generating a solution sequence is not quite the same problem, but it seemed interesting and I'm hoping that someone comes up with a clever way to structure the data in order to make it efficient to search for these near collisions.

Answer 1

Here's a terrible, brute force way of generating a sequence. I haven't attempted to do much to make it fast, though there are probably several simple gains to be had here. I'm trying to think of a way to make this at least a couple of orders of magnitude faster rather than finding improvements of a few percent.

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;
}