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

Question

Pandigital number - это число, которое содержит цифры 1. длина номера.
Например, 123, 4312 и 967412385.

Я решил много задач Project Euler, но проблемы Pandigital всегда превышают правило одной минуты.

Это моя пандигитальная функция:

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

Создайте свою собственную функцию и протестируйте ее с помощью этого метода

int pans=0;
for (int i=123456789;i<=123987654;i++){
    if (isPandigital(i)){
         pans++;
    }
}

Используя этот цикл, вы должны получить 720 пандигитальных чисел. Мое среднее время составляло 500 миллисекунд.

Я использую Java, но вопрос открыт для любого языка.

UPDATE
Ответ @andras пока что лучший, но ответ @Sani Huttunen вдохновил меня на добавление нового алгоритма, который почти совпадает с @ andras.

Answer 1

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

Answer 2

Прямой путь

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

Answer 3

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

  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)

Answer 4

В 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

Answer 5

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

Простая реализация.Перебор и вычисление примерно за 140 мс

Answer 6

Я рефакторил ответ Андраса для 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

Answer 7

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

}

Answer 8

Эта реализация на c # примерно на 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: Кажется, что мода (%) стоит дорого в C #. Если мы заменим использование оператора 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;
}

РЕДАКТИРОВАТЬ: интеграция 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;
}