Самый быстрый алгоритм проверки, является ли число pandigital?

Ответ 1

С#, 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:

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

Чтобы перечислить числа в указанном диапазоне, достаточно было бы генерировать перестановки.

Следующее не является ответом на ваш вопрос в строгом смысле слова, поскольку он не выполняет проверку. Он использует универсальную реализацию перестановок, не оптимизированную для этого особого случая - он все равно генерирует необходимые 720 перестановок за 13 мс (разрывы строк могут быть испорчены):

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

Ответ 2

Это мое решение:

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 секунды на моей (довольно медленной) системе.

Ответ 3

Две вещи, которые вы можете улучшить:

• Вам не нужно использовать набор: вы можете использовать логический массив с 10 элементами
• Вместо преобразования в строку используйте деление и операцию по модулю (%) для извлечения цифр.

Ответ 4

Использование битового вектора для отслеживания того, какие цифры были найдены, является самым быстрым методом raw. Есть два способа улучшить его:

• Проверьте, является ли число делимым на 9. Это необходимое условие для pandigital, поэтому мы можем исключить 88% номеров спереди.

• Используйте умножение и сдвиги вместо делений, если ваш компилятор не делает этого для вас.

Это дает следующее, которое запускает тестовый тест примерно на 3 мс на моей машине. Он правильно идентифицирует 9-значные цифровые цифровые номера 362880 между 100000000 и 999999999.

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

Ответ 5

Мое решение включает в себя суммы и продукты. Это в С# и работает примерно на 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;
}

Ответ 6

Зачем искать, когда вы можете их создать?

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

Ответ 7

J делает это красиво:

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

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

Но медленно. Я передумаю. На данный момент синхронизация выполняется на 4,8 секунды.

EDIT:

Если это только между двумя заданными числами, 123456789 и 123987654, то это выражение:

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

Работает через 0,23 секунды. Это примерно так же быстрый, грубый стиль, как он попадает в J.

Ответ 8

TheMachineCharmer прав. По крайней мере, для некоторых проблем лучше перебирать все пандиталы, проверяя каждый, чтобы увидеть, соответствует ли он критериям проблемы. Тем не менее, я думаю, что их код не совсем прав.

Я не уверен, какой из них лучше в этом случае: Публикация нового ответа или редактирование их. В любом случае, здесь приведен модифицированный код Python, который, как я считаю, является правильным, хотя он не генерирует pandigitals 0-to-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()

Ответ 9

Вы можете добавить:

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

Это приведет к короткому замыканию многих ваших вычислений, поскольку оно вернет false, как только будет найден дубликат, поскольку add() возвращает false в этом случае.

Ответ 10

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

Ответ 11

У меня есть решение для генерации Pandigital чисел с использованием StringBuffers в Java. На моем ноутбуке мой код занимает в общей сложности 5 мс для запуска. Из этого требуется только 1 мс для генерации перестановок с использованием StringBuffers; остальные 4ms необходимы для преобразования этого StringBuffer в int [].

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

Этот код также может использоваться для генерации всех номеров Pandigital (исключая нуль). Просто измените вызов создания объекта на

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

Это означает, что префикса нет, и перестановки должны начинаться с "1" и продолжаться до тех пор, пока длина цифр не будет равна 9.

Ниже приведены измерения времени для разных длин. @andras: Можете ли вы попробовать запустить свой код для создания девятизначных номеров Pandigital? Сколько времени займет?

Ответ 12

Эта реализация С# примерно на 8% быстрее, чем @andras в диапазоне от 123456789 до 123987654, но на моем тестовом поле действительно трудно увидеть, как он работает в 14 мс, а этот работает в 13 мс.

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<<count)-1 == digits>>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,4 мс, а эта реализация составляет в среднем 13,2 мс

EDIT: Похоже, что mod (%) стоит дорого в С#. Если мы заменим использование оператора mod на ручную кодированную версию, то эта реализация будет в среднем 11 мс на 100 запусков.

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

EDIT: Интегрированное 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;
}

Ответ 13

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

Простая реализация. Brute-принудительно и вычисляет около 140 мс

Ответ 14

В Java

Вы всегда можете просто сгенерировать их и преобразовать строки в целые числа, что быстрее для больших чисел

public static List<String> permutation(String str) {
    List<String> permutations = new LinkedList<String>();
    permutation("", str, permutations);
    return permutations;
}

private static void permutation(String prefix, String str, List<String> 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 number

Ответ 15

Я решил использовать что-то вроде этого:

  def is_pandigital(n, zero_full=True, base=10):
    """Returns True or False if the number n is pandigital.

    This function returns True for formal pandigital numbers as well as
    n-pandigital
    """
    r, l = 0, 0
    while n:
        l, r, n = l + 1, r + n % base, n / base
    t = xrange(zero_full ^ 1, l + (zero_full ^ 1))
    return r == sum(t) and l == len(t)

Ответ 16

Прямой путь

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

Ответ 17

Я реорганизовал ответ Андраса для Свифта:

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

Ответ 18

отличные ответы, мои 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;

}