Todos los xenodromos

15

Introducción

Un xenodrome en base n es un número entero donde todos sus dígitos en base n son diferentes. Aquí hay algunas secuencias OEIS de xenodromos.

Por ejemplo, en base 16, FACE, 42y FEDCBA9876543210son algunos xenodromes (que son 64206, 66y 18364758544493064720en base 10), pero 11y DEFACEDno lo son.

Desafío

Dada una base de entrada, n , emite todos los xenódromos para esa base en la base 10 .

La salida debe estar en orden de menor a mayor. Debe quedar claro dónde termina un término en la secuencia y comienza uno nuevo (por ejemplo, [0, 1, 2]está claro dónde 012no está).

n será un número entero mayor que 0.

Aclaraciones

Este desafío hace IO específicamente en la base 10 para evitar el manejo de enteros y su base como cadenas. El desafío está en manejar de manera abstracta cualquier base. Como tal, estoy agregando esta regla adicional:

Los enteros no se pueden almacenar como cadenas en una base que no sea la base 10.

Su programa debería ser capaz de manejar teóricamente razonablemente alto n si no hubiera tiempo, memoria, precisión u otras restricciones técnicas en la implementación de un lenguaje.

Este es el , por lo que el programa más corto, en bytes, gana.

Ejemplo de entrada y salida

1  # Input
0  # Output
2
0, 1, 2
3
0, 1, 2, 3, 5, 6, 7, 11, 15, 19, 21
4
0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 18, 19, 24, 27, 28, 30, 33, 35, 36, 39, 44, 45, 49, 50, 52, 54, 56, 57, 75, 78, 99, 108, 114, 120, 135, 141, 147, 156, 177, 180, 198, 201, 210, 216, 225, 228
Artyer
fuente
1
¿hay un límite para n?
FlipTack
@ Flp.Tkc No. Debe poder manejar n razonablemente alto. No quiero que el desafío esté limitado por cuán alta puede manejar la conversión de base integrada de un idioma.
Artyer
@Artyer Eso debería haber sido parte del texto del desafío, entonces. Parece que algunas respuestas ya lo están haciendo
Luis Mendo
Sé que la conversión de base en Pyth puede manejar valores mayores que 36 , pero dado que esto quiere todos los xenódromos, la pitón subyacente se rompe cuando la lista se vuelve demasiado grande, diciendo que no cabe un valor en a ssize_t. ¿Se está rompiendo de esta manera aceptable?
FryAmTheEggman
2
Alguien parece haber rechazado todas las respuestas que no pueden manejar bases más grandes debido a un límite de precisión incorporado, que también parece una implementación en lugar de un problema de algoritmo. ¿Podrías aclarar?
Dennis

Respuestas:

10

Pyth , 8 bytes

f{IjTQU^

Filtra los números en [0, n ^ n - 1] al no tener elementos duplicados en la base n . La conversión de base en Pyth funcionará con cualquier base, pero como se ve en una lista de números que aumenta rápidamente, eventualmente no podrá almacenar los valores en la memoria.

Pruébalo en línea!

Explicación:

f{IjTQU^QQ    - Auto-fill variables
      U^QQ    - [0, n^n-1]
f             - keep only those that ...
 {I           - do not change when deduplicated
   jTQ        - are converted into base n
FryAmTheEggman
fuente
¡Guau, una solución más corta que la solución Jelly que hizo Dennis! : 'P
HyperNeutrino
3
Nadie le gana a Jelly. ¶:
Roman Gräf
5

Python 2, 87 bytes

n=input()
for x in range(n**n):
 s={n};a=x
 while{a%n}|s>s:s|={a%n};a/=n
 print-~-a*`x`

Imprime líneas en blanco adicionales para no xenodromos:

golf % python2.7 xenodromes.py <<<3
0
1
2
3

5
6
7



11



15



19

21
Lynn
fuente
5

Jalea , 9 8 bytes

ð*ḶbQ€Qḅ

¡Gracias a @JonathanAllan por jugar golf en 1 byte!

Pruébalo en línea! o verificar todos los casos de prueba .

Cómo funciona

ð*ḶbQ€Qḅ  Main link. Argument: n

ð         Make the chain dyadic, setting both left and right argument to n.
          This prevents us from having to reference n explicitly in the chain.
 *        Compute nⁿ.
  Ḷ       Unlength; yield A := [0, ..., nⁿ - 1].
   b      Convert each k in A to base n.
    Q€    Unique each; remove duplicate digits.
      Q   Unique; remove duplicate digit lists.
       ḅ  Convert each digit list from base n to integer.
Dennis
fuente
4

Jalea , 12 bytes

*`ḶbµQ⁼$Ðfḅ³

TryItOnline!

Funcionará para cualquiera n, con suficiente memoria, la conversión de base de Jelly no es restrictiva.

¿Cómo?

*`ḶbµQ⁼$Ðfḅ³ - Main link: n
    µ        - monadic chain separation
*            - exponentiation with
 `           - repeated argument, i.e. n^n
  Ḷ          - lowered range, i.e. [0,1,2,...,n^n-1]
   b         - covert to base n (vectorises)
        Ðf   - filter keep:
       $     -     last two links as a monad
     Q       -         unique elements
      ⁼      -         equals input (no vectorisation)
           ³ - first program argument (n)
          ḅ  - convert from base (vectorises)
Jonathan Allan
fuente
3

JavaScript (ES7), 86 bytes

n=>{a=[];for(i=n**n;i--;j||a.unshift(i))for(j=i,b=0;(b^=f=1<<j%n)&f;j=j/n|0);return a}
Neil
fuente
Falla para 1(Debería salir [0], pero RangeErrors.)
Artyer
Exactamente lo que tenía, pero esto fallaría teóricamente 37si la precisión no fuera un problema, lo que creo que lo invalida ...
ETHproductions
@Artyer He portado mi versión de Batch, por lo que ahora funcionará ndesde antes 1hasta que la 13precisión de punto flotante la mate.
Neil
Me gusta cómo las soluciones comienzan realmente cortas, y luego de repente saltan un orden de magnitud.
Nissa
2

Perl 6 , 47 bytes

{(0..$_**$_).grep: !*.polymod($_ xx*).repeated}

Devuelve una Seq . ( Seq es un contenedor Iterable básico para Iterator s)

Con una entrada de 16toma 20 segundos para calcular el elemento 53905 de la Seq ( 87887).

Expandido:

{       # bare block lambda with implicit parameter 「$_」

  ( 0 .. ($_ ** $_) )    # Range of values to be tested

  .grep:                 # return only those values

    !\                   # Where the following isn't true
    *\                   # the value
    .polymod( $_ xx * )  # when put into the base being tested
    .repeated            # has repeated values
  }
}
Brad Gilbert b2gills
fuente
2

Lote, 204 200 bytes

@set/an=%1,m=1
@for /l %%i in (1,1,%1)do @set/am*=n
@for /l %%i in (0,1,%m%)do @set/ab=0,j=i=%%i&call:l
@exit/b
:l
@set/a"f&=b^=f=1<<j%%n,j/=n"
@if %f%==0 exit/b
@if %j% gtr 0 goto l
@echo %i%

No funcionará para n> 9 porque Batch solo tiene aritmética de 32 bits. Convenientemente, Batch evalúa f &= b ^= f = 1 << j % ncomo en f = 1 << j % n, b = b ^ f, f = f & blugar de f = f & (b = b ^ (f = 1 << j % n)).

Neil
fuente
2

Mathematica, 59 48 bytes

Select[Range[#^#]-1,xMax[x~DigitCount~#]==1]&

Contiene el carácter U + F4A1 "Uso privado"

Explicación

Range[#^#]-1

Generar {1, 2, ..., n^n}. Restar 1. (rendimientos {0, 1, ..., n^n - 1})

xMax[x~DigitCount~#]==1

Una función booleana: Truesi cada dígito ocurre como máximo una vez en la base n.

Select[ ... ]

De la lista {0, 1, ..., n^n - 1}, seleccione los que dan Truecuando se aplica la función booleana anterior.

Versión de 59 bytes

Select[Range[#^#]-1,xDuplicateFreeQ[x~IntegerDigits~#]]&
JungHwan Min
fuente
2

Mathematica, 48 55 bytes

Union[(x   x~FromDigits~#)/@Permutations[Range@#-1,#]]&

(El espacio triple entre xs debe ser reemplazado por el carácter de 3 bytes \ uF4A1 para que el código funcione).

Función sin nombre de un único argumento. En lugar de probar enteros para determinar la xenodromicidad, simplemente genera todas las permutaciones posibles de subconjuntos de los dígitos permitidos (lo que evita automáticamente la repetición) y convierte los enteros correspondientes en la base 10. Cada xenodrome se genera dos veces, con y sin un 0 inicial; Unionelimina los duplicados y ordena la lista para arrancar.

Greg Martin
fuente
1
Falla por 2. La función da {0, 1}. Creo que necesitas en Permutations[Range@#-1, #]lugar de Subsets[Range@#-1].
JungHwan Min
Gah, qué error tan descabellado. ¡Gracias por observarlo y por sugerir la solución perfecta!
Greg Martin