检查一个数字是否是全数字的最快算法是什么？

Question

全数字数是指包含数字1..数字长度的数字。
例如123、4312和967412385。

我已经解决了许多欧拉项目问题，但全数字问题始终超过一分钟规则。

这是我的全数字函数：

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个全数字数字。我的平均时间是500毫秒。

我正在使用Java，但问题适用于任何语言。

更新
@andras的答案目前是最快的，但@Sani Huttunen的答案启发了我添加一个新的算法，它几乎与@andras的时间相同。

- mohdajami

---

也许你的思路有误。不确定你面临的问题是什么，但我相信解决方案一定比简单地循环数字并检查数字是否为全数字更加聪明。而且，每个数字都必须恰好出现一次吗？这也是一个与_math_相关的网站，不仅仅是编程... - Aryabhatta

std::next_permutation? - kennytm

为什么要找，当你可以自己创造呢？ ;) - Pratik Deoghare

@Psytronic，我认为我是按照欧拉计划的定义来做的，但不太确定... - Aryabhatta

所有基于计算数字和乘积的解决方案都是错误的。例如，它们接受124445799作为全数字数，因为数字的总和为45，乘积为362880。目前至少有3个不正确的解决方案。因此，我建议更改您测试的区间。 - Accipitridae

Answer 1

C#，17毫秒，如果你真的想要一个检查。

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

对于在十进制下与维基百科定义一致的检查：

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

---

为了列举您给定范围内的数字，生成排列即可。以下并不是严格意义上对您问题的回答，因为它没有实现检查。它使用通用的排列实现，未优化这种特殊情况 - 它仍然在13毫秒内生成所需的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();
    }
}

- Andras Vass

---

我已经尝试了你的算法，在Java中它大约需要35毫秒，我非常印象深刻 :) - mohdajami

@medopal：谢谢。 :) 我已经更新了。你能否用Java试一下？ - Andras Vass

@andras，哇，它的运行时间减少了一半，在Java中只需要20毫秒，做得好 :) - mohdajami

我的计算是在一台Macbook上完成的，使用Java 5。我的PC需要更多时间。我认为我们无法做得比这更少，应该称之为“安德拉斯全数字算法” :) - mohdajami

"if ((tmp = digits) == (digits |= 1 << (n - ((n / 10) * 10) - 1)))" 有点令人困惑，为什么不拆分一下呢？但是解决方案非常好！ - schirrmacher

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秒。

- Michael Borgwardt

Answer 3

你可以改进的两件事：

• 您不需要使用set：可以使用带有10个元素的布尔数组
• 使用除法和模运算（%）提取数字，而不是转换为字符串。

- Mark Byers

---

第一个技巧是要跟踪设置的最高和最低标志。如果您尝试两次设置相同的标志，则会出现重复 - 否则，您希望在最后min = 1且max = expected_max。 - user180247

Answer 4

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

1. 检查数字是否可被9整除。这是成为全数字的必要条件，因此我们可以排除前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;
}

- Jeffrey Sax

---

我印象深刻 :). 我会在Java中尝试并回报。 - mohdajami

@Moberg 它使用64位算术乘以2^32/9，然后向左移动32位。 - Jeffrey Sax

Answer 5

我的解决方案涉及求和和求积。 这是用C#编写的，在我的笔记本电脑上运行大约需要180毫秒：

static int[] sums = new int[] {1, 3, 6, 10, 15, 21, 28, 36, 45};
static int[] products = new int[] {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

static void Main(string[] args)
{
  var pans = 0;
  for (var i = 123456789; i <= 123987654; i++)
  {
    var num = i.ToString();
    if (Sum(num) == sums[num.Length - 1] && Product(num) == products[num.Length - 1])
      pans++;
  }
  Console.WriteLine(pans);
}

protected static int Sum(string num)
{
  int sum = 0;
  foreach (char c in num)
    sum += (int) (c - '0');

  return sum;
}

protected static int Product(string num)
{
  int prod = 1;
  foreach (char c in num)
    prod *= (int)(c - '0');

  return prod;
}

- Sani Huttunen

Answer 6

为什么要寻找它们，而不是自己制造它们呢？

from itertools import *

def generate_pandigital(length):
    return (''.join for each in list(permutations('123456789',length)))

def test():
    for i in range(10):
        print i
        generate_pandigital(i)

if __name__=='__main__':
    test()

- Pratik Deoghare

---

好主意，但我认为代码中有一些小问题。请看我的回答：https://dev59.com/7XE95IYBdhLWcg3wDpYG#2486099 - Tyler

好主意，但是在欧拉计划中的任务是找到所有长度为41（10 ** 40数字）的排列，它是全数字且也是步数（每个数字要么比前一个数字+1，要么比前一个数字-1，除了9（只能-1）和0（只能+1））。所以不仅仅是全数字。 - Stefan Gruenwald

Answer 7

TheMachineCharmer是正确的。对于一些问题，至少要遍历所有的全数字数，检查每一个数字是否符合问题的条件。然而，我认为他们的代码不太正确。

在这种情况下，我不确定哪种更好的SO礼仪：发布新答案还是编辑他们的答案。无论如何，这是经过修改的Python代码，我认为它是正确的，尽管它不生成0到n的全数字数。

from itertools import *

def generate_pandigital(length):
    'Generate all 1-to-length pandigitals'
    return (''.join(each) for each in list(permutations('123456789'[:length])))

def test():
    for i in range(10):
        print 'Generating all %d-digit pandigitals' % i
        for (n,p) in enumerate(generate_pandigital(i)):
            print n,p

if __name__=='__main__':
    test()

- Tyler

Answer 8

J做得很好：

    isPandigital =: 3 : 0
        *./ (' ' -.~ ": 1 + i. # s) e. s =. ": y
    )
isPandigital"0 (123456789 + i. 1 + 123987654 - 123456789)

但是速度较慢，需要修改。目前运行时间为4.8秒。

编辑:

如果只在123456789和123987654两个数之间进行比较，则可以使用以下表达式：

    *./"1 (1+i.9) e."1 (9#10) #: (123456789 + i. 1 + 123987654 - 123456789)

这将在0.23秒内运行。这是J语言中最快的暴力方法之一。

- MPelletier

Answer 9

bool IsPandigital (unsigned long n) {
  if (n <= 987654321) {
      hash_map<int, int> m;
      unsigned long count = (unsigned long)(log((double)n)/log(10.0))+1;

      while (n) {
          ++m[n%10];
          n /= 10;
      }

      while (m[count]==1 && --count);

      return !count;
  }

  return false;
}

bool IsPandigital2 (unsigned long d) {
  // Avoid integer overflow below if this function is passed a very long number
  if (d <= 987654321) {
      unsigned long sum = 0;
      unsigned long prod = 1;
      unsigned long n = d;

      unsigned long max = (log((double)n)/log(10.0))+1;
      unsigned long max_sum = max*(max+1)/2;
      unsigned long max_prod = 1;

      while (n) {
          sum += n % 10;
          prod *= (n%10);
          max_prod *= max;
          --max;
          n /= 10;
      }

      return (sum == max_sum) && (prod == max_prod);
  }

- Sameer

---

@Sameer，请问您能否添加每个算法的执行时间（以毫秒为单位）？ - mohdajami

Answer 10

我有一个使用Java中的StringBuffers生成Pandigital数字的解决方案。 在我的笔记本电脑上，我的代码总共需要5ms运行时间。 其中仅需要1ms来使用StringBuffers生成排列；其余4ms用于将此StringBuffer转换为int[]。

@medopal：您能检查一下此代码在您的系统上所需的时间吗？

public class GenPandigits 
{

 /**
 * The prefix that must be appended to every number, like 123.
 */
int prefix;

/**
 * Length in characters of the prefix.
 */
int plen;

/**
 * The digit from which to start the permutations
 */
String beg;

/**
 * The length of the required Pandigital numbers.
 */
int len;

/**
 * @param prefix If there is no prefix then this must be null
 * @param beg If there is no prefix then this must be "1"
 * @param len Length of the required numbers (excluding the prefix)
 */
public GenPandigits(String prefix, String beg, int len)
{
    if (prefix == null) 
    {
        this.prefix = 0;
        this.plen = 0;
    }
    else 
    {
        this.prefix = Integer.parseInt(prefix);
        this.plen = prefix.length();
    }
    this.beg = beg;
    this.len = len;
}
public StringBuffer genPermsBet()
{
    StringBuffer b = new StringBuffer(beg);
    for(int k=2;k<=len;k++)
    {
        StringBuffer rs = new StringBuffer();
        int l = b.length();
        int s = l/(k-1);
        String is = String.valueOf(k+plen);
        for(int j=0;j<k;j++)
        {
            rs.append(b);
            for(int i=0;i<s;i++)
            {
                rs.insert((l+s)*j+i*k+j, is);
            }
        }
        b = rs;
    }
    return b;
}

public int[] getPandigits(String buffer)
{
    int[] pd = new int[buffer.length()/len];
    int c= prefix;
    for(int i=0;i<len;i++)
        c =c *10;
    for(int i=0;i<pd.length;i++)
        pd[i] = Integer.parseInt(buffer.substring(i*len, (i+1)*len))+c;
    return pd;
}
public static void main(String[] args) 
{
    GenPandigits gp = new GenPandigits("123", "4", 6);

    //GenPandigits gp = new GenPandigits(null, "1", 6);

    long beg = System.currentTimeMillis();
    StringBuffer pansstr = gp.genPermsBet();
    long end = System.currentTimeMillis();
    System.out.println("Time = " + (end - beg));
    int pd[] = gp.getPandigits(pansstr.toString());
    long end1 = System.currentTimeMillis();
    System.out.println("Time = " + (end1 - end));
    }
}

这段代码也可以用于生成所有的全数字数（不包括零）。只需将对象创建调用更改为

GenPandigits gp = new GenPandigits(null, "1", 9);

这意味着没有前缀，排列必须从“1”开始，并继续到数字长度为9。

以下是不同长度的时间测量。 @andras：您能否尝试运行代码以生成九位数全数字数？需要多长时间？

- athena