examples - algorithms book
Encuentra todos los números de vampiros de 4 dígitos (16)
Estoy resolviendo un problema para descubrir todos los números de Vampiro de 4 dígitos.
Un número de vampiro v = x * y se define como un número con ''n'' número par de dígitos formados al multiplicar un par de números de ''n / 2'' dígitos (donde los dígitos se toman del número original en cualquier orden) x y y juntos. Si v es un número de vampiro, entonces xey se llaman sus "colmillos".
Ejemplos de números de vampiros son:
1. 1260=21*60
2. 1395=15*93
3. 1530=30*51
He probado el algoritmo de fuerza bruta para combinar diferentes dígitos de un número dado y multiplicarlos juntos. Pero este método es altamente ineficiente y toma mucho tiempo.
¿Hay una solución algorítmica más eficiente para este problema?
1260 1395 1435 1530 1827 2187 6880 es vampiro
Soy nuevo en la programación ... Pero solo hay 12 combinaciones para encontrar todos los números de vampiros de 4 dígitos. Mi pobre respuesta es:
public class VampNo {
public static void main(String[] args) {
for(int i = 1000; i < 10000; i++) {
int a = i/1000;
int b = i/100%10;
int c = i/10%10;
int d = i%10;
if((a * 10 + b) * (c * 10 + d) == i || (b * 10 + a) * (d * 10 + c) == i ||
(a * 10 + d) * (b * 10 + c) == i || (d * 10 + a) * (c * 10 + b) == i ||
(a * 10 + c) * (b * 10 + d) == i || (c * 10 + a) * (d * 10 + b) == i ||
(a * 10 + b) * (d * 10 + c) == i || (b * 10 + a) * (c * 10 + d) == i ||
(b * 10 + c) * (d * 10 + a) == i || (c * 10 + b) * (a * 10 + d) == i ||
(a * 10 + c) * (d * 10 + b) == i || (c * 10 + a) * (b * 10 + d) == i)
System.out.println(i + " is vampire");
}
}
}
La tarea principal ahora es simplificar la expresión booleana en el bloque If ()
Al igual que alguien mencionado anteriormente, mi método es encontrar primero todas las permutaciones de un número, luego dividirlas a la mitad para formar dos números de 2 dígitos y probar si su producto es igual al número original.
Otra discusión interesante anterior es cuántas permutaciones puede tener un número. Aquí está mi opinión: (1) un número cuyos cuatro digitales son iguales tiene 1 permutación; (2) un número que tiene solo dos dígitos diferentes tiene 6 permutaciones (no importa si contiene ceros, porque no nos importa después de la permutación si todavía es un número de 4 dígitos); (3) un número que tiene tres dígitos diferentes tiene 12 permutaciones; (4) un número con los cuatro dígitos diferentes tiene 24 permutaciones.
public class VampireNumber {
// method to find all permutations of a 4-digit number
public static void permuta(String x, String s, int v)
{for(int i = 0; i < s.length(); i++)
{permuta( x + s.charAt(i), s.substring(0,i) + s.substring(i+1), v);
if (s.length() == 1)
{x = x + s;
int leftpart = Integer.parseInt(x.substring(0,2));
int rightpart = Integer.parseInt(x.substring(2));
if (leftpart*rightpart == v)
{System.out.println("Vampir = " + v);
}
}
}
}
public static void main(String[] args){
for (int i = 1000; i < 10000; i++) {
permuta("", Integer.toString(i), i); //convert the integer to a string
}
}
}
EDITAR: fuerza bruta completa que elimina los valores idénticos de X e Y ...
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Vampire {
public static void main(String[] args) {
for (int x = 10; x < 100; x++) {
String sx = String.valueOf(x);
for (int y = x; y < 100; y++) {
int v = x * y;
String sy = String.valueOf(y);
String sv = String.valueOf(v);
if (sortVampire(sx + sy).equals(sortVampire(sv))) {
System.out.printf("%d * %d = %d%n", x, y, v);
}
}
}
}
private static List<Character> sortVampire(String v) {
List<Character> vc = new ArrayList<Character>();
for (int j = 0; j < v.length(); j++) {
vc.add(v.charAt(j));
}
Collections.sort(vc);
return vc;
}
}
El enfoque que trataría sería recorrer cada número en [1000, 9999], y probar si alguna permutación de sus dígitos (dividir en el medio) se multiplicó para hacerlo.
Esto requerirá (9999 - 1000) * 24 = 215,976 pruebas, que deben ejecutarse aceptablemente rápido en una máquina moderna.
Definitivamente almacenaría los dígitos por separado, por lo que puedes evitar tener que hacer algo así como un grupo de divisiones para extraer los dígitos de un solo entero.
Si escribe su código de modo que solo haga adiciones y multiplicaciones enteras (y tal vez la división ocasional para llevar), debería ser bastante rápido. Puede aumentar aún más la velocidad omitiendo pares de dos dígitos que "obviamente" no funcionarán, por ejemplo, aquellos con ceros a la izquierda (tenga en cuenta que el producto más grande que puede producirse con un dígito y uno de dos dígitos es 9 * 99 u 891).
También tenga en cuenta que este enfoque es vergonzosamente paralelo ( http://en.wikipedia.org/wiki/Embarrassingly_parallel ), por lo que si realmente necesita acelerarlo aún más, debería buscar probar los números en hilos separados.
Este código python se ejecuta muy rápido (O (n2))
result = []
for i in range(10,100):
for j in range(10, 100):
list1 = []
list2 = []
k = i * j
if k < 1000 or k > 10000:
continue
else:
for item in str(i):
list1.append(item)
for item in str(j):
list1.append(item)
for item in str(k):
list2.append(item)
flag = 1
for each in list1:
if each not in list2:
flag = 0
else:
list2.remove(each)
for each in list2:
if each not in list1:
flag = 0
if flag == 1:
if k not in result:
result.append(k)
for each in result:
print(each)
Este es un hack feo (fuerza bruta, comprobación manual de permutaciones, operaciones de buffer inseguras, produce duplicados, etc.) pero cumple su función. Tu nuevo ejercicio es mejorarlo: P
Wikipedia afirma que hay 7 números de vampiros que tienen 4 dígitos de longitud. El código completo los ha encontrado a todos , incluso algunos duplicados.
Editar: Aquí hay una función de comparación ligeramente mejor.
Editar 2: Aquí hay una versión de C ++ que resultados únicos (por lo tanto evita duplicados) usando un std::map (y almacena la última ocurrencia del número de vampiro particular junto con sus factores en él). También cumple el criterio de que al menos uno de los factores no debe terminar con 0 , es decir, un número no es un número de vampiro si ambos multiplicandos son divisibles para entonces. Esta prueba busca números de vampiros de 6 dígitos y de hecho encuentra exactamente 148 de ellos, de acuerdo con lo que Wikipedia dice.
El código original:
#include <stdio.h>
void getdigits(char buf[], int n)
{
while (n) {
*buf++ = n % 10;
n /= 10;
}
}
int is_vampire(const char n[4], const char i[2], const char j[2])
{
/* maybe a bit faster if unrolled manually */
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
// et cetera, the following 20 repetitions are redacted for clarity
// (this really should be a loop, shouldn''t it?)
return 0;
}
int main()
{
for (int i = 10; i < 100; i++) {
for (int j = 10; j < 100; j++) {
int n = i * j;
if (n < 1000)
continue;
char ndigits[4];
getdigits(ndigits, n);
char idigits[2];
char jdigits[2];
getdigits(idigits, i);
getdigits(jdigits, j);
if (is_vampire(ndigits, idigits, jdigits))
printf("%d * %d = %d/n", i, j, n);
}
}
return 0;
}
He editado el algoritmo de Owlstead un poco para hacerlo más comprensible para principiantes / aprendices de Java.
import java.util.Arrays;
public class Vampire {
public static void main(String[] args) {
for (int x = 10; x < 100; x++) {
String sx = Integer.toString(x);
for (int y = x; y < 100; y++) {
int v = x * y;
String sy = Integer.toString(y);
String sv = Integer.toString(v);
if( Arrays.equals(sortVampire(sx + sy), sortVampire(sv)))
System.out.printf("%d * %d = %d%n", x, y, v);
}
}
}
private static char[] sortVampire (String v){
char[] sortedArray = v.toCharArray();
Arrays.sort(sortedArray);
return sortedArray;
}
}
Itere sobre todos los posibles colmillos (100 x 100 = 10000 posibilidades) y busca si su producto tiene los mismos dígitos que los colmillos.
La iteración me parece bien, ya que solo necesita hacer esto una vez para encontrar todos los valores y luego puede guardarlos en la memoria caché. La versión de Python (3) tarda aproximadamente 1,5 segundos:
# just some setup
from itertools import product, permutations
dtoi = lambda *digits: int(''''.join(str(digit) for digit in digits))
gen = ((dtoi(*digits), digits) for digits in product(range(10), repeat=4) if digits[0] != 0)
l = []
for val, digits in gen:
for check1, check2 in ((dtoi(*order[:2]), dtoi(*order[2:])) for order in permutations(digits) if order[0] > 0 and order[2] > 0):
if check1 * check2 == val:
l.append(val)
break
print(l)
Que le dará [1260, 1395, 1435, 1530, 1827, 2187, 6880]
Me parece que para realizar la menor cantidad posible de pruebas sin depender de ninguna comprensión particularmente abstracta, es probable que desee iterar sobre los colmillos y descartar a los candidatos obviamente inútiles.
Por ejemplo, dado que x*y == y*x aproximadamente la mitad del espacio de búsqueda se puede eliminar solo evaluando los casos donde y > x . Si el colmillo más grande de dos dígitos es 99, entonces el más pequeño que puede hacer un número de cuatro dígitos es 11, por lo tanto, no comience por debajo de 11.
EDITAR:
OK, arrojando todo lo que pensaba en la mezcla (a pesar de que parece tonto en comparación con la solución líder).
for (x = 11; x < 100; x++)
{
/* start y either at x, or if x is too small then 1000 / x */
for (y = (x * x < 1000 ? 1000 / x : x); y < 100; y++)
{
int p = x * y;
/* if sum of digits in product is != sum of digits in x+y, then skip */
if ((p - (x + y)) % 9 != 0)
continue;
if (is_vampire(p, x, y))
printf("%d/n", p);
}
}
y la prueba, ya que no he visto a nadie usar un histograma, aún:
int is_vampire(int p, int x, int y)
{
int h[10] = { 0 };
int i;
for (i = 0; i < 4; i++)
{
h[p % 10]++;
p /= 10;
}
for (i = 0; i < 2; i++)
{
h[x % 10]--;
h[y % 10]--;
x /= 10;
y /= 10;
}
for (i = 0; i < 10; i++)
if (h[i] != 0)
return 0;
return 1;
}
No habría renunciado tan fácilmente a la fuerza bruta. Tiene un conjunto distinto de números, 1000 a 9999 que debe ejecutar. Me gustaría dividir el conjunto en una serie de subconjuntos, y luego girar los hilos para manejar cada subconjunto.
Podrías dividir aún más el trabajo con las diferentes combinaciones de cada número; IIRC mi matemática discreta, tiene 4 * 3 * 2 o 24 combinaciones para cada número para probar.
Un enfoque productor / consumidor puede valer la pena.
O puede usar una propiedad de números de vampiros descrita en users.cybercity.dk/~dsl522332/math/vampires (vinculada desde Wikipedia):
Un resultado teórico importante encontrado por Pete Hartley:
If x·y is a vampire number then x·y == x+y (mod 9)Prueba: Sea mod el operador del módulo binario y d (x) la suma de los dígitos decimales de x. Es bien sabido que d (x) mod 9 = x mod 9, para todo x. Supongamos que x · y es un vampiro. Luego contiene los mismos dígitos que xey, y en particular d (x · y) = d (x) + d (y). Esto lleva a: (x · y) mod 9 = d (x · y) mod 9 = (d (x) + d (y)) mod 9 = (d (x) mod 9 + d (y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9 = (x + y) mod 9
Las soluciones a la congruence son (x mod 9, y mod 9) en {(0,0), (2,2), (3,6), (5,8), (6,3), (8, 5)}
Entonces su código podría verse así:
for(int i=18; i<100; i=i+9){ // 18 is the first multiple of 9 greater than 10
for(int j=i; j<100; j=j+9){ // Start at i because as @sh1 said it''s useless to check both x*y and y*x
checkVampire(i,j);
}
}
for(int i=11; i<100; i=i+9){ // 11 is the first number greater than 10 which is = 2 mod 9
for(int j=i; j<100; j=j+9){
checkVampire(i,j);
}
}
for(int i=12; i<100; i=i+9){
for(int j=i+3; j<100; j=j+9){
checkVampire(i,j);
}
}
for(int i=14; i<100; i=i+9){
for(int j=i+3; j<100; j=j+9){
checkVampire(i,j);
}
}
// We don''t do the last 2 loops, again for symmetry reasons
Como son 40 elementos en cada uno de los conjuntos como {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100} , solo hace 4*40 = 160 iteraciones, cuando una fuerza bruta le da 104 iteraciones. Puede hacer incluso menos operaciones si tiene en cuenta la restricción >= 1000 , por ejemplo, puede evitar comprobar si j < 1000/i .
Ahora puedes escalar fácilmente para encontrar vampiros con más de 4 dígitos =)
Otra versión de fuerza bruta (C), con una clase de burbuja libre para iniciar ...
#include <stdio.h>
static inline void bubsort(int *p)
{ while (1)
{ int s = 0;
for (int i = 0; i < 3; ++i)
if (p[i] > p[i + 1])
{ s = 1;
int t = p[i]; p[i] = p[i + 1]; p[i + 1] = t;
}
if (!s) break;
}
}
int main()
{ for (int i = 10; i < 100; ++i)
for (int j = i; j < 100; ++j)
{ int p = i * j;
if (p < 1000) continue;
int xd[4];
xd[0] = i % 10;
xd[1] = i / 10;
xd[2] = j % 10;
xd[3] = j / 10;
bubsort(xd);
int x = xd[0] + xd[1] * 10 + xd[2] * 100 + xd[3] * 1000;
int yd[4];
yd[0] = p % 10;
yd[1] = (p / 10) % 10;
yd[2] = (p / 100) % 10;
yd[3] = (p / 1000);
bubsort(yd);
int y = yd[0] + yd[1] * 10 + yd[2] * 100 + yd[3] * 1000;
if (x == y)
printf("%2d * %2d = %4d/n", i, j, p);
}
return 0;
}
Funciona casi instantáneamente. Los nombres de variables no son demasiado descriptivos, pero deberían ser bastante obvios ...
La idea básica es comenzar con dos posibles colmillos, dividirlos en dígitos y ordenar los dígitos para facilitar la comparación. Luego hacemos lo mismo con el producto: desglosarlo en dígitos y ordenarlo. Luego volvemos a constituir dos enteros a partir de los dígitos ordenados, y si son iguales, tenemos una coincidencia.
Posibles mejoras: 1) inicie j en 1000 / i lugar de i para evitar tener que hacerlo if (p < 1000) ... , 2) tal vez use sortid de inserción en lugar de sort de burbuja (¿pero quién notará esos 2 intercambios adicionales?) , 3) usar una implementación real swap() , 4) comparar las matrices directamente en lugar de construir un entero sintético a partir de ellas. Sin embargo, no estoy seguro de que alguno de ellos haga una diferencia medible, a menos que lo ejecute en un Commodore 64 o algo así ...
Editar: Solo por curiosidad, tomé esta versión y la generalicé un poco más para trabajar en los casos de 4, 6 y 8 dígitos. Sin ninguna optimización importante, puede encontrar todos los números de vampiros de 8 dígitos en <10 segundos. .
Versión de fuerza bruta en C # con LINQ:
class VampireNumbers
{
static IEnumerable<int> numberToDigits(int number)
{
while(number > 0)
{
yield return number % 10;
number /= 10;
}
}
static bool isVampire(int first, int second, int result)
{
var resultDigits = numberToDigits(result).OrderBy(x => x);
var vampireDigits = numberToDigits(first)
.Concat(numberToDigits(second))
.OrderBy(x => x);
return resultDigits.SequenceEqual(vampireDigits);
}
static void Main(string[] args)
{
var vampires = from fang1 in Enumerable.Range(10, 89)
from fang2 in Enumerable.Range(10, 89)
where fang1 < fang2
&& isVampire(fang1, fang2, fang1 * fang2)
select new { fang1, fang2 };
foreach(var vampire in vampires)
{
Console.WriteLine(vampire.fang1 * vampire.fang2
+ " = "
+ vampire.fang1
+ " * "
+ vampire.fang2);
}
}
}
Y aquí está mi código. Para generar números zombie, necesitamos usar la clase Random :)
import java.io.PrintStream;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
class VampireNumbers {
static PrintStream p = System.out;
private static Set<Integer> findVampireNumber() {
Set<Integer> vampireSet = new HashSet<Integer>();
for (int y = 1000; y <= 9999; y++) {
char[] numbersSeparately = ("" + y).toCharArray();
int numberOfDigits = numbersSeparately.length;
for (int i = 0; i < numberOfDigits; i++) {
for (int j = 0; j < numberOfDigits; j++) {
if (i != j) {
int value1 = Integer.valueOf("" + numbersSeparately[i] + numbersSeparately[j]);
int ki = -1;
for (int k = 0; k < numberOfDigits; k++) {
if (k != i && k != j) {
ki = k;
}
}
int kj = -1;
for (int t = 0; t < numberOfDigits; t++) {
if (t != i && t != j && t != ki) {
kj = t;
}
}
int value21 = Integer.valueOf("" + numbersSeparately[ki] + numbersSeparately[kj]);
int value22 = Integer.valueOf("" + numbersSeparately[kj] + numbersSeparately[ki]);
if (value1 * value21 == y && !(numbersSeparately[j] == 0 && numbersSeparately[kj] == 0)
|| value1 * value22 == y
&& !(numbersSeparately[j] == 0 && numbersSeparately[ki] == 0)) {
vampireSet.add(y);
}
}
}
}
}
return vampireSet;
}
public static void main(String[] args) {
Set<Integer> vampireSet = findVampireNumber();
Iterator<Integer> i = vampireSet.iterator();
int number = 1;
while (i.hasNext()) {
p.println(number + ": " + i.next());
number++;
}
}
}
<?php
for ($i = 10; $i <= 99; $j++) {
// Extract digits
$digits = str_split($i);
// Loop through 2nd number
for ($j = 10; $j <= 99; $j++) {
// Extract digits
$j_digits = str_split($j);
$digits[2] = $j_digits[0];
$digits[3] = $j_digits[1];
$product = $i * $j;
$product_digits = str_split($product);
// check if fangs
$inc = 0;
while (in_array($digits[$inc], $product_digits)) {
// Remove digit from product table
/// So AAAA -> doesnt match ABCD
unset($product_digits[$array_serach($digits[$inc], $product_digits)]);
$inc++;
// If reached 4 -> vampire number
if ($inc == 4) {
$vampire[] = $product;
break;
}
}
}
}
// Print results
print_r($vampire);
?>
Tomó menos de un segundo en PHP. Ni siquiera podía decir que tenía que ejecutar 8100 cálculos ... ¡las computadoras son rápidas!
Resultados:
Te da los 4 dígitos más algunos se repiten. Puede procesar los datos y eliminar duplicados.