medopal - 5 months ago 23
Java Question

# Fastest algorithm to check if a number is pandigital?

Pandigital number is a number that contains the digits 1..number length.

For example 123, 4312 and 967412385.

I have solved many Project Euler problems, but the Pandigital problems always exceed the one minute rule.

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

I'm using Java, but the question is open to any language.

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.

C#, 17ms, if you really want a check.

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

For a check that is consistent with the Wikipedia definition in base 10:

``````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):

``````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)
{
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);
}
}

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

#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);