java 检查数字是否为泛数字的最快算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2484892/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest algorithm to check if a number is pandigital?
提问by medopal
Pandigital number is a number that contains the digits 1..number length.
For example 123, 4312 and 967412385.
Pandigital 数字是包含数字 1..number 长度的数字。
例如 123、4312 和 967412385。
I have solved many Project Euler problems, but the Pandigital problems always exceed the one minute rule.
我已经解决了很多 Project Euler 问题，但是 Pandigital 问题总是超过一分钟规则。
This is my pandigital function:
这是我的泛数字函数：
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();
}
Create your own function and test it with this method
创建您自己的函数并使用此方法对其进行测试
int pans=0;
for (int i=123456789;i<=123987654;i++){
if (isPandigital(i)){
pans++;
}
}
Using this loop, you should get 720 pandigital numbers. My average time was 500 millisecond.
使用这个循环，你应该得到 720 个泛数字。我的平均时间是 500 毫秒。
I'm using Java, but the question is open to any language.
我正在使用 Java，但这个问题对任何语言都是开放的。
UPDATE
@andras answer has the best time so far, but @Sani Huttunen answer inspired me to add a new algorithm, which gets almost the same time as @andras.
到目前为止，更新@andras 答案的时间最好，但@Sani Huttunen 的答案启发我添加了一个新算法，该算法的时间与@andras 几乎相同。
采纳答案by Andras Vass
C#, 17ms, if you really want a check.
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();
}
}
For a check that is consistent with the Wikipedia definitionin base 10:
对于与基数 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;
}
To enumerate numbers in the range you have given, generating permutations would suffice.
要枚举您给出的范围内的数字，生成排列就足够了。
The following is not an answer to your question in the strict sense, since it does not implement a check. It uses a generic permutation implementation not optimized for this special case - it still generates the required 720 permutations in 13ms (line breaks might be messed up):
以下不是严格意义上的问题的答案，因为它没有实施检查。它使用了一个没有针对这种特殊情况进行优化的通用排列实现——它仍然在 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();
}
}
回答by Michael Borgwardt
This is my solution:
这是我的解决方案：
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]);
}
Runs the loop in 0.3 seconds on my (rather slow) system.
在我的（相当慢的）系统上在 0.3 秒内运行循环。
回答by Jeffrey Sax
Using a bit vector to keep track of which digits have been found appears to be the fastest raw method. There are two ways to improve it:
使用位向量来跟踪找到了哪些数字似乎是最快的原始方法。有两种方法可以改进它：
Check if the number is divisible by 9. This is a necessary condition for being pandigital, so we can exclude 88% of numbers up front.
Use multiplication and shifts instead of divisions, in case your compiler doesn't do that for you.
检查数字是否可以被 9 整除。这是泛数字的必要条件，因此我们可以预先排除 88% 的数字。
使用乘法和移位而不是除法，以防您的编译器不为您这样做。
This gives the following, which runs the test benchmark in about 3ms on my machine. It correctly identifies the 362880 9-digit pan-digital numbers between 100000000 and 999999999.
这给出了以下内容，它在我的机器上运行了大约 3 毫秒的测试基准。它可以正确识别 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;
}
回答by Mark Byers
Two things you can improve:
你可以改进的两件事：
- You don't need to use a set: you can use a boolean array with 10 elements
- Instead of converting to a string, use division and the modulo operation (%) to extract the digits.
- 您不需要使用集合：您可以使用具有 10 个元素的布尔数组
- 不是转换为字符串，而是使用除法和模运算 (%) 来提取数字。
回答by Sani Singh Huttunen
My solution involves Sums and Products. This is in C# and runs in about 180ms on my laptop:
我的解决方案涉及总和和产品。这是在 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;
}
回答by Pratik Deoghare
Why find when you can make them?
为什么要找到什么时候可以制作它们？
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()
回答by MPelletier
Jdoes this nicely:
J做得很好：
isPandigital =: 3 : 0
*./ (' ' -.~ ": 1 + i. # s) e. s =. ": y
)
isPandigital"0 (123456789 + i. 1 + 123987654 - 123456789)
But slowly. I will revise. For now, clocking at 4.8 seconds.
但是慢慢来。我会修改。目前，时钟为 4.8 秒。
EDIT:
编辑：
If it's just between the two set numbers, 123456789 and 123987654, then this expression:
如果它只是在两个集合数字 123456789 和 123987654 之间，那么这个表达式：
*./"1 (1+i.9) e."1 (9#10) #: (123456789 + i. 1 + 123987654 - 123456789)
Runs in 0.23 seconds. It's about as fast, brute-force style, as it gets in J.
运行时间为 0.23 秒。它与 J 中的速度、蛮力风格一样快。
回答by MatrixFrog
TheMachineCharmer is right. At least for some the problems, it's better to iterate over all the pandigitals, checking each one to see if it fits the criteria of the problem. However, I think their code is not quite right.
TheMachineCharmer 是对的。至少对于某些问题，最好迭代所有泛数字，检查每个泛数字是否符合问题的标准。但是，我认为他们的代码不太正确。
I'm not sure which is better SO etiquette in this case: Posting a new answer or editing theirs. In any case, here is the modified Python code which I believe to be correct, although it doesn't generate 0-to-n pandigitals.
在这种情况下，我不确定哪种礼仪更好：发布新答案或编辑他们的答案。无论如何，这是我认为正确的修改后的 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()
回答by Reed Copsey
回答by Sameer
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);
}
