Schnellster Algorithmus, um zu überprüfen, ob eine Nummer pandigital ist?

C#, 17ms, wenn Sie wirklich wollen, eine überprüfen.

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

Einer Kontrolle, die im Einklang mit der Wikipedia-definition in der Basis 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;
}

Auflisten von zahlen in den Bereich, den Sie gegeben haben, generieren von Permutationen, würde genügen.

Der folgenden ist nicht eine Antwort auf Ihre Frage im engeren Sinne, da es nicht einen check implementieren. Es verwendet ein generisches permutation Umsetzung nicht optimiert sind für diesen speziellen Fall - es immer noch erzeugt die erforderliche 720 Permutationen in 13ms (Zeilenumbrüche werden könnte, Durcheinander):

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

InformationsquelleAutor der Antwort Andras Vass

Zwei Dinge, die Sie verbessern können:

• Sie nicht brauchen, um einen Satz: Sie können mit einem boolean-array mit 10 Elementen
• Anstelle der Umwandlung in einen string verwenden, der division und der modulo-operation (%) zum extrahieren der Ziffern.

InformationsquelleAutor der Antwort Mark Byers

Meine Lösung beinhaltet die Summen und Produkte.
Dies ist in C# und führt in etwa 180ms auf meinem laptop:

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

InformationsquelleAutor der Antwort Sani Singh Huttunen

J hat dies sehr schön:

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

 isPandigital"0 (123456789 + ich. 1 + 123987654 - 123456789) 

Aber langsam. Werde ich überarbeiten. Für jetzt, Taktung bei 4,8 Sekunden.

EDIT:

Wenn es nur zwischen den beiden zahlen, 123456789 und 123987654, dann dieser Ausdruck:

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

Läuft in 0.23 Sekunden. Es ist in etwa so schnell, brute-force-Stil, wie es nur geht, in J.

InformationsquelleAutor der Antwort MPelletier

Könnte man hinzufügen:

 if (set.add(c)==false) return false;

Diese kurze Strecke zu einer Menge Ihrer Berechnungen, denn es wird false zurückgegeben, sobald ein Duplikat gefunden wurde, da hinzufügen() gibt false zurück, in diesem Fall.

InformationsquelleAutor der Antwort Reed Copsey

Habe ich eine Lösung für die Generierung von Pandigital zahlen mit StringBuffers in Java. Auf meinem laptop, mein code braucht insgesamt 5ms ausgeführt. Dieses nur 1 MS erforderlich ist für die Generierung der Permutationen mit StringBuffers; die übrigen 4ms sind erforderlich für die Umwandlung dieser StringBuffer ein int[].

@medopal: Können Sie in der Zeit, wo dieser code wird auf Ihrem system?

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

Dieser code kann auch verwendet werden zum erzeugen alle Pandigital zahlen(ohne null). Ändern Sie einfach die Objekt-Erstellung Aufruf

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

Dies bedeutet, dass es kein Präfix, und die Permutationen muss von "1" und fahren Fort, bis die Länge der zahlen ist 9.

Folgenden werden die Messungen der Zeit für verschiedene Längen.

@andras: Können Sie versuchen, und führen Sie Ihren code zu generieren, der neun Ziffern Pandigital zahlen? Welche Zeit dauert es?

InformationsquelleAutor der Antwort athena

#include <cstdio>
#include <ctime>

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

Einfache Umsetzung. Brute-forced und berechnet in etwa 140 ms

InformationsquelleAutor der Antwort smac89

Entschied ich mich, etwas zu verwenden, wie diese:

 def is_pandigital(n, zero_full=True, base=10): 
 """Gibt True zurück, oder False, wenn die Zahl n ist pandigital. 

 Diese Funktion gibt True zurück, für die formale pandigital zahlen sowie 
 n-pandigital 
 """ 
 r, l = 0, 0 
 während n: 
 l, r, n = l + 1, r + n % base, n /base 
 t = xrange(zero_full ^ 1, l + (zero_full ^ 1)) 
 Rentabilität r = = - Summe(t) und l == len(t) 

InformationsquelleAutor der Antwort Krolique

Ich umgestaltet Andras' Antwort für 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

InformationsquelleAutor der Antwort schirrmacher