最快的算法来检查一个数字是否是pandigital？
Pandigital数字是一个包含数字1..number长度的数字。
例如123,4312和967412385。
我已经解决了许多Project Euler问题，但Pandigital问题总是超过一分钟规则。
这是我的pandigitalfunction：
private boolean isPandigital(int n){ Set set= new TreeSet(); 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，但问题是对任何语言开放。
UPDATE
@andra答案到目前为止是最好的时间，但是@Sani Huttunen的回答激发了我添加一个新的算法，它几乎与@andras相同。
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 { /// /// Generates permutations. /// /// Type of items to permute. /// Array of items. Will not be modified. /// Optional comparer to use. /// If a Permutations of input items. public static IEnumerable> Permute(T[] items, IComparer 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: EW 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> Permute (T[] items) { return Permute(items, null); } public static IEnumerable> Permute (IEnumerable items, IComparer comparer) { List list = new List (items); return Permute(list.ToArray(), comparer); } public static IEnumerable> Permute (IEnumerable items) { return Permute(items, null); } #endregion Overloads #region Utility public static IEnumerable ApplyTransform ( T[] items, IntPair[] transform) { for (int i = 0; i < transform.Length; i++) { yield return items[transform[i].Second]; } } public static void Swap (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(); } }
这是我的解决方案：
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秒的速度运行循环。
你可以改进两件事：
- 您不需要使用集合：您可以使用包含10个元素的布尔数组
- 而不是转换为字符串，使用除法和模运算（％）来提取数字。
使用位向量来跟踪已找到的数字似乎是最快的原始方法。 有两种方法可以改善它：
-
检查数字是否可被9整除。这是pandigital的必要条件，因此我们可以预先排除88％的数字。
-
如果您的编译器不为您执行此操作，请使用乘法和移位而不是除法。
这给出了以下内容，它在我的机器上运行大约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; }
我的解决方案涉及Sums和Products。 这是在C＃中，在我的笔记本电脑上运行大约180ms：
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; }
为什么找到什么时候可以制作它们？
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()
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中的快速，蛮力风格一样快。
TheMachineCharmer是对的。 至少对于某些问题，最好迭代所有的pandigitals，检查每个pandigitals以查看它是否符合问题的标准。 但是，我认为他们的代码并不完全正确。
在这种情况下，我不确定哪种更好的礼仪：发布新答案或编辑他们的答案。 在任何情况下，这里都是修改后的Python代码，我认为它是正确的，尽管它不会生成0到n的pandigitals。
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()
你可以添加：
if (set.add(c)==false) return false;
这会使很多计算发生短路，因为一旦发现重复，它就会返回false，因为在这种情况下add（）返回false。
bool IsPandigital (unsigned long n) { if (n <= 987654321) { hash_map 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); }
我有一个使用Java中的StringBuffers生成Pandigital数字的解决方案。 在我的笔记本电脑上，我的代码总共需要5毫秒才能运行。 其中，使用StringBuffers生成排列只需要1ms; 将此StringBuffer转换为int []需要剩余的4ms。
@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
这意味着没有前缀，并且排列必须从“1”开始并继续直到数字的长度为9。
以下是不同长度的时间测量。 
@andras：您可以尝试运行代码来生成九位数的Pandigital数字吗？ 现在几点钟？
在123456789到123987654的范围内，这个c＃实现比@andras快8％左右，但是在我的测试盒上很难看到它在14ms内运行并且这个运行时间为13ms。
static bool IsPandigital(int n) { int count = 0; int digits = 0; int digit; int bit; do { digit = n % 10; if (digit == 0) { return false; } bit = 1 << digit; if (digits == (digits |= bit)) { return false; } count++; n /= 10; } while (n > 0); return (1<>1; }
如果我们平均100次运行的结果，我们可以得到一个小数点。
public void Test() { int pans = 0; var sw = new Stopwatch(); sw.Start(); for (int count = 0; count < 100; count++) { pans = 0; for (int i = 123456789; i <= 123987654; i++) { if (IsPandigital(i)) { pans++; } } } sw.Stop(); Console.WriteLine("{0}pcs, {1}ms", pans, sw.ElapsedMilliseconds / 100m); }
@andras实现平均为14.4ms，这个实现平均为13.2ms
编辑：似乎mod（％）在c＃中很昂贵。 如果我们用手动编码版本替换mod运算符的使用，那么这个实现在100次运行中平均为11ms。
private static bool IsPandigital(int n) { int count = 0; int digits = 0; int digit; int bit; do { digit = n - ((n / 10) * 10); if (digit == 0) { return false; } bit = 1 << digit; if (digits == (digits |= bit)) { return false; } count++; n /= 10; } while (n > 0); return (1 << count) - 1 == digits >> 1; }
编辑：在数字计算中集成n / = 10，以提高速度。
private static bool IsPandigital(int n) { int count = 0; int digits = 0; int digit; int bit; do { digit = n - ((n /= 10) * 10); if (digit == 0) { return false; } bit = 1 << digit; if (digits == (digits |= bit)) { return false; } count++; } while (n > 0); return (1 << count) - 1 == digits >> 1; }
#include #include bool isPandigital(long num) { int arr [] = {1,2,3,4,5,6,7,8,9}, G, count = 9; do { G = num%10; if (arr[G-1]) --count; arr[G-1] = 0; } while (num/=10); return (!count); } int main() { clock_t start(clock()); int pans=0; for (int i = 123456789;i <= 123987654; ++i) { if (isPandigital(i)) ++pans; } double end((double)(clock() - start)); printf("\n\tFound %d Pandigital numbers in %lf seconds\n\n", pans, end/CLOCKS_PER_SEC); return 0; }
简单的实施。 暴力强制并在大约140毫秒内计算
在Java中
您始终可以生成它们，并将字符串转换为整数，这对于较大的数字更快
public static List permutation(String str) { List permutations = new LinkedList (); permutation("", str, permutations); return permutations; } private static void permutation(String prefix, String str, List permutations) { int n = str.length(); if (n == 0) { permutations.add(prefix); } else { for (int i = 0; i < n; i++) { permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n), permutations); } } }
以下代码适用于测试数字pandigitality。
对于你的测试，我的跑步时间约为50毫秒
1-9 PanDigital
public static boolean is1To9PanDigit(int i) { if (i < 1e8) { return false; } BitSet set = new BitSet(); while (i > 0) { int mod = i % 10; if (mod == 0 || set.get(mod)) { return false; } set.set(mod); i /= 10; } return true; }
或更一般，1到N，
public static boolean is1ToNPanDigit(int i, int n) { BitSet set = new BitSet(); while (i > 0) { int mod = i % 10; if (mod == 0 || mod > n || set.get(mod)) { return false; } set.set(mod); i /= 10; } return set.cardinality() == n; }
只是为了好玩，0到9，由于前导零，零需要额外的逻辑
public static boolean is0To9PanDigit(long i) { if (i < 1e6) { return false; } BitSet set = new BitSet(); if (i <= 123456789) { // count for leading zero set.set(0); } while (i > 0) { int mod = (int) (i % 10); if (set.get(mod)) { return false; } set.set(mod); i /= 10; } return true; }
也用于设置迭代边界：
public static int maxPanDigit(int n) { StringBuffer sb = new StringBuffer(); for(int i = n; i > 0; i--) { sb.append(i); } return Integer.parseInt(sb.toString()); } public static int minPanDigit(int n) { StringBuffer sb = new StringBuffer(); for(int i = 1; i <= n; i++) { sb.append(i); } return Integer.parseInt(sb.toString()); }
您可以轻松使用此代码生成通用的MtoNPanDigital数字检查器
我决定使用这样的东西：
def is_pandigital（n，zero_full = True，base = 10）：
msgstr“”“如果数字n是pandigital，则返回True或False。
对于正式的pandigital数字，此函数返回True
正pandigital
“””
r，l = 0,0
而n：
l，r，n = 1 + 1，r + n％碱，n /碱
t = xrange（zero_full ^ 1，l +（zero_full ^ 1））
return r == sum（t）和l == len（t）
直线前进
boolean isPandigital(int num,int length){ for(int i=1;i<=length;i++){ if(!(num+"").contains(i+"")) return false; } return true; }
或者，如果您确定该号码已经是正确的长度
static boolean isPandigital(int num){ for(int i=1;i<=(num+"").length();i++){ if(!(num+"").contains(i+"")) return false; } return true; }
我重构了Andras对Swift的回答：
extension Int { func isPandigital() -> Bool { let requiredBitmask = 0b1111111111; let minimumPandigitalNumber = 1023456789; if self >= minimumPandigitalNumber { var resultBitmask = 0b0; var digits = self; while digits != 0 { let lastDigit = digits % 10; let binaryCodedDigit = 1 << lastDigit; resultBitmask |= binaryCodedDigit; // remove last digit digits /= 10; } return resultBitmask == requiredBitmask; } return false; } } 1023456789.isPandigital(); // true
很棒的答案，我的2美分
bool IsPandigital(long long number, int n){ int arr[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, amax = 0, amin; while (number > 0){ int rem = number % 10; arr[rem]--; if (arr[rem] < 0) return false; number = number / 10; } for (int i = 0; i < n; i++){ if (i == 0) amin = arr[i]; if (arr[i] > amax) amax = arr[i]; if (arr[i] < amin) amin = arr[i]; } if (amax == 0 && amin == 0) return true; else return false;
}