StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>C#, 17ms, if you really want a <em>check</em>.</p> <pre><code>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(); } } </code></pre> <p>For a check that is consistent with the <a href="http://en.wikipedia.org/wiki/Pandigital_number" rel="noreferrer">Wikipedia definition</a> in base 10:</p> <pre><code>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; } </code></pre> <hr> <p>To enumerate numbers in the range you have given, generating permutations would suffice. </p> <p>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):</p> <pre><code>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(); } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload