最快的算法来检查一个数字是否是pandigital？

Question

Pandigital数字是一个包含数字1..number长度的数字.
例如123,4312和967412385.

我已经解决了许多Project Euler问题,但Pandigital问题总是超过一分钟规则.

这是我的pandigital功能:

private boolean isPandigital(int n){
    Set<Character> set= new TreeSet<Character>();   
    String string = n+"";
    for (char c:string.toCharArray()){
        if (c=='0') return false;
        set.add(c);
    }
    return set.size()==string.length();
}

创建自己的函数并使用此方法对其进行测试

int pans=0;
for (int i=123456789;i<=123987654;i++){
    if (isPandigital(i)){
         pans++;
    }
}

使用这个循环,你应该得到720个pandigital数字.我的平均时间是500毫秒.

我正在使用Java,但问题是对任何语言开放.

更新
@andras答案到目前为止是最好的时间,但是@Sani Huttunen的回答激发了我添加一个新的算法,它几乎与@andras相同.

Answer 1

C#,17ms,如果你真的想要一张支票.

class Program
{
    static bool IsPandigital(int n)
    {
        int digits = 0; int count = 0; int tmp;

        for (; n > 0; n /= 10, ++count)
        {
            if ((tmp = digits) == (digits |= 1 << (n - ((n / 10) * 10) - 1)))
                return false;
        }

        return digits == (1 << count) - 1;
    }

    static void Main()
    {
        int pans = 0;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 123456789; i <= 123987654; i++)
        {
            if (IsPandigital(i))
            {
                pans++;
            }
        }
        sw.Stop();
        Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

对于与基数10中的Wikipedia定义一致的检查:

const int min = 1023456789;
const int expected = 1023;

static bool IsPandigital(int n)
{
    if (n >= min)
    {
        int digits = 0;

        for (; n > 0; n /= 10)
        {
            digits |= 1 << (n - ((n / 10) * 10));
        }

        return digits == expected;
    }
    return false;
}

要枚举您给出的范围内的数字,生成排列就足够了.

以下不是严格意义上的问题的答案,因为它没有实施检查.它使用了一个没有针对这种特殊情况进行优化的通用置换实现 - 它仍然在13ms内生成所需的720个排列(换行符可能会混乱):

static partial class Permutation
{
    /// <summary>
    /// Generates permutations.
    /// </summary>
    /// <typeparam name="T">Type of items to permute.</typeparam>
    /// <param name="items">Array of items. Will not be modified.</param>
    /// <param name="comparer">Optional comparer to use.
    /// If a <paramref name="comparer"/> is supplied, 
    /// permutations will be ordered according to the 
    /// <paramref name="comparer"/>
    /// </param>
    /// <returns>Permutations of input items.</returns>
    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items, IComparer<T> comparer)
    {
        int length = items.Length;
        IntPair[] transform = new IntPair[length];
        if (comparer == null)
        {
            //No comparer. Start with an identity transform.
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(i, i);
            };
        }
        else
        {
            //Figure out where we are in the sequence of all permutations
            int[] initialorder = new int[length];
            for (int i = 0; i < length; i++)
            {
                initialorder[i] = i;
            }
            Array.Sort(initialorder, delegate(int x, int y)
            {
                return comparer.Compare(items[x], items[y]);
            });
            for (int i = 0; i < length; i++)
            {
                transform[i] = new IntPair(initialorder[i], i);
            }
            //Handle duplicates
            for (int i = 1; i < length; i++)
            {
                if (comparer.Compare(
                    items[transform[i - 1].Second], 
                    items[transform[i].Second]) == 0)
                {
                    transform[i].First = transform[i - 1].First;
                }
            }
        }

        yield return ApplyTransform(items, transform);

        while (true)
        {
            //Ref: E. W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1997
            //Find the largest partition from the back that is in decreasing (non-icreasing) order
            int decreasingpart = length - 2;
            for (;decreasingpart >= 0 && 
                transform[decreasingpart].First >= transform[decreasingpart + 1].First;
                --decreasingpart) ;
            //The whole sequence is in decreasing order, finished
            if (decreasingpart < 0) yield break;
            //Find the smallest element in the decreasing partition that is 
            //greater than (or equal to) the item in front of the decreasing partition
            int greater = length - 1;
            for (;greater > decreasingpart && 
                transform[decreasingpart].First >= transform[greater].First; 
                greater--) ;
            //Swap the two
            Swap(ref transform[decreasingpart], ref transform[greater]);
            //Reverse the decreasing partition
            Array.Reverse(transform, decreasingpart + 1, length - decreasingpart - 1);
            yield return ApplyTransform(items, transform);
        }
    }

    #region Overloads

    public static IEnumerable<IEnumerable<T>> Permute<T>(T[] items)
    {
        return Permute(items, null);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items, IComparer<T> comparer)
    {
        List<T> list = new List<T>(items);
        return Permute(list.ToArray(), comparer);
    }

    public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> items)
    {
        return Permute(items, null);
    }

    #endregion Overloads

    #region Utility

    public static IEnumerable<T> ApplyTransform<T>(
        T[] items, 
        IntPair[] transform)
    {
        for (int i = 0; i < transform.Length; i++)
        {
            yield return items[transform[i].Second];
        }
    }

    public static void Swap<T>(ref T x, ref T y)
    {
        T tmp = x;
        x = y;
        y = tmp;
    }

    public struct IntPair
    {
        public IntPair(int first, int second)
        {
            this.First = first;
            this.Second = second;
        }
        public int First;
        public int Second;
    }

    #endregion
}

class Program
{

    static void Main()
    {
        int pans = 0;
        int[] digits = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        Stopwatch sw = new Stopwatch();
        sw.Start();
        foreach (var p in Permutation.Permute(digits))
        {
            pans++;
            if (pans == 720) break;
        }
        sw.Stop();
        Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds);
        Console.ReadKey();
    }
}

Answer 2

这是我的解决方案:

static char[][] pandigits = new char[][]{
        "1".toCharArray(),
        "12".toCharArray(),
        "123".toCharArray(),
        "1234".toCharArray(),
        "12345".toCharArray(),
        "123456".toCharArray(),
        "1234567".toCharArray(),
        "12345678".toCharArray(),
        "123456789".toCharArray(),
};
private static boolean isPandigital(int i)
{
    char[] c = String.valueOf(i).toCharArray();
    Arrays.sort(c);
    return Arrays.equals(c, pandigits[c.length-1]);
}

在我的(相当慢的)系统上以0.3秒的速度运行循环.

Answer 3

你可以改进两件事:

• 您不需要使用集合:您可以使用包含10个元素的布尔数组
• 而不是转换为字符串,使用除法和模运算(%)来提取数字.

Answer 4

使用位向量来跟踪已找到的数字似乎是最快的原始方法.有两种方法可以改善它:

1. 检查数字是否可被9整除.这是pandigital的必要条件,因此我们可以预先排除88%的数字.

2. 如果您的编译器不为您执行此操作,请使用乘法和移位而不是除法.

这给出了以下内容,它在我的机器上运行测试基准大约3ms.它可以正确识别100000000和999999999之间的362880个9位数字泛数字.

bool IsPandigital(int n)
{
    if (n != 9 * (int)((0x1c71c71dL * n) >> 32))
        return false;

    int flags = 0;
    while (n > 0) {
        int q = (int)((0x1999999aL * n) >> 32);
        flags |= 1 << (n - q * 10);
        n = q;
    }
    return flags == 0x3fe;
}