recursivo - ordenamiento de quicksort java
¿Algoritmo más rápido para verificar si un número es pandigital? (18)
El número pandigital es un número que contiene los dígitos 1..número de longitud.
Por ejemplo 123, 4312 y 967412385.
He resuelto muchos problemas del Proyecto Euler, pero los problemas de Pandigital siempre exceden la regla de un minuto.
Esta es mi función 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();
}
Crea tu propia función y pruébala con este método.
int pans=0;
for (int i=123456789;i<=123987654;i++){
if (isPandigital(i)){
pans++;
}
}
Usando este bucle, deberías obtener 720 números pandigitales. Mi tiempo promedio fue de 500 milisegundos.
Estoy usando Java, pero la pregunta está abierta a cualquier idioma.
ACTUALIZAR
La respuesta de @andras tiene el mejor momento hasta el momento, pero la respuesta de @Sani Huttunen me inspiró a agregar un nuevo algoritmo, que recibe casi el mismo tiempo que @andras.
¿Por qué encontrar cuándo puedes hacerlas?
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()
C #, 17ms, si realmente quieres un cheque .
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();
}
}
Para una verificación que sea consistente con la definición de Wikipedia en la 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;
}
Para enumerar números en el rango que ha dado, sería suficiente generar permutaciones.
Lo siguiente no es una respuesta a su pregunta en sentido estricto, ya que no implementa una verificación. Utiliza una implementación de permutación genérica no optimizada para este caso especial; aún genera las 720 permutaciones requeridas en 13 ms (los saltos de línea pueden estar desordenados):
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();
}
}
De manera directa
boolean isPandigital(int num,int length){
for(int i=1;i<=length;i++){
if(!(num+"").contains(i+""))
return false;
}
return true;
}
O si está seguro de que el número ya tiene la longitud correcta
static boolean isPandigital(int num){
for(int i=1;i<=(num+"").length();i++){
if(!(num+"").contains(i+""))
return false;
}
return true;
}
Decidí usar algo como esto:
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)
Dos cosas que puedes mejorar:
- No necesitas usar un conjunto: puedes usar una matriz booleana con 10 elementos
- En lugar de convertir a una cadena, use la división y la operación de módulo (%) para extraer los dígitos.
El uso de un vector de bits para realizar un seguimiento de los dígitos encontrados parece ser el método en bruto más rápido. Hay dos formas de mejorarlo:
Compruebe si el número es divisible entre 9. Esta es una condición necesaria para ser pandigital, por lo que podemos excluir el 88% de los números por adelantado.
Use la multiplicación y los turnos en lugar de las divisiones, en caso de que su compilador no lo haga por usted.
Esto da lo siguiente, que ejecuta la prueba de referencia en aproximadamente 3 ms en mi máquina. Identifica correctamente los 362880 números pan-digitales de 9 dígitos entre 100000000 y 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;
}
En java
Siempre puede simplemente generarlos y convertir las cadenas en enteros, que es más rápido para números más grandes
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);
}
}
}
El siguiente código funciona para probar una pandigitalidad de números.
Para tu prueba la mía corrió en unos ~ 50ms.
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;
}
o más general, 1 a 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;
}
Y solo por diversión, de 0 a 9, cero requiere lógica adicional debido a un cero inicial.
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;
}
También para establecer los límites de iteración:
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());
}
Podría usar fácilmente este código para generar un verificador de números genérico de MtoNPanDigital
Esta es mi solución:
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]);
}
Ejecuta el bucle en 0,3 segundos en mi sistema (bastante lento).
Esta implementación de C # es aproximadamente un 8% más rápida que @andras en el rango de 123456789 a 123987654, pero es realmente difícil de ver en mi caja de prueba ya que se ejecuta en 14 ms y esta en 13 ms.
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;
}
Si promediamos los resultados de 100 carreras, podemos obtener un punto decimal.
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);
}
La implementación de @andras promedia 14.4ms y esta implementación promedia 13.2ms
EDITAR: Parece que mod (%) es caro en c #. Si reemplazamos el uso del operador mod con una versión codificada a mano, entonces esta implementación promedia 11ms sobre 100 ejecuciones.
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;
}
EDITAR: Integró n / = 10 en el cálculo de dígitos para una pequeña mejora de velocidad.
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;
}
Mi solución involucra sumas y productos. Esto está en C # y se ejecuta en aproximadamente 180 ms en mi computadora portátil:
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;
}
Replanté la respuesta de Andras para 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
Tengo una solución para generar números Pandigital usando StringBuffers en Java. En mi computadora portátil, mi código toma un total de 5 ms para ejecutarse. De esto solo se requiere 1 ms para generar las permutaciones utilizando StringBuffers; los 4 ms restantes son necesarios para convertir este StringBuffer en un int [].
@medopal: ¿Puede verificar el tiempo que toma este código en su sistema?
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));
}
}
Este código también se puede utilizar para generar todos los números Pandigital (excluyendo cero). Solo cambia la llamada de creación de objeto a
GenPandigits gp = new GenPandigits(null, "1", 9);
Esto significa que no hay prefijo, y las permutaciones deben comenzar desde "1" y continuar hasta que la longitud de los números sea 9.
Las siguientes son las medidas de tiempo para diferentes longitudes. @andras: ¿Puedes intentar ejecutar tu código para generar los números Pandigital de nueve dígitos? A que hora te lleva
TheMachineCharmer tiene razón. Al menos para algunos de los problemas, es mejor iterar sobre todos los pandigitales, verificando cada uno para ver si cumple con los criterios del problema. Sin embargo, creo que su código no es del todo correcto.
No estoy seguro de cuál es la mejor etiqueta de SO en este caso: publicar una nueva respuesta o editar la de ellos. En cualquier caso, aquí está el código Python modificado que creo que es correcto, aunque no genera pandigitales de 0 a 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()
Usted podría agregar:
if (set.add(c)==false) return false;
Esto causaría un corto circuito en muchos de sus cálculos, ya que devolverá falso tan pronto como se encuentre un duplicado, ya que add() devuelve falso en este caso.
grandes respuestas, mis 2 centavos
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;
}
J hace esto muy bien:
isPandigital =: 3 : 0 *./ ('' '' -.~ ": 1 + i. # s) e. s =. ": y ) isPandigital"0 (123456789 + i. 1 + 123987654 - 123456789)
Pero despacio. Voy a revisar Por ahora, registrando 4.8 segundos.
EDITAR:
Si es solo entre los dos números establecidos, 123456789 y 123987654, entonces esta expresión:
*./"1 (1+i.9) e."1 (9#10) #: (123456789 + i. 1 + 123987654 - 123456789)
Corre en 0.23 segundos. Es casi tan rápido como el estilo de fuerza bruta, como llega a J.
#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;
}
Implementación simple. Fuerza bruta y computa en unos 140 ms.
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);
}