All the Xenodromes

Question

Introduction

A xenodrome in base n is an integer where all of its digits in base n are different. Here are some OEIS sequences of xenodromes.

For example, in base 16, FACE, 42 and FEDCBA9876543210 are some xenodromes (Which are 64206, 66 and 18364758544493064720 in base 10), but 11 and DEFACED are not.

Challenge

Given an input base, n, output out all xenodromes for that base in base 10.

The output should be in order of least to greatest. It should be clear where a term in the sequence ends and a new one begins (e.g. [0, 1, 2] is clear where 012 is not.)

n will be an integer greater than 0.

Clarifications

This challenge does IO specifically in base 10 to avoid handling integers and their base as strings. The challenge is in abstractly handling any base. As such, I am adding this additional rule:

Integers cannot be stored as strings in a base other than base 10.

Your program should be able to theoretically handle reasonably high n if there were no time, memory, precision or other technical restrictions in the implementation of a language.

This is code-golf, so the shortest program, in bytes, wins.

Example Input and Output

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

Answer 1

Pyth, 8 bytes

f{IjTQU^

Filters the numbers in [0, n^n - 1] on having no duplicate elements in base n. The base conversion in Pyth will work with any base, but since this looks at a very quickly increasing list of numbers, it will eventually be unable to store the values in memory.

Try it online!

Explanation:

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

Answer 2

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`

Prints extra blank lines for non-xenodromes:

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

5
6
7



11



15



19

21

Answer 3

Jelly, 9 8 bytes

ð*ḶbQ€Qḅ

Thanks to @JonathanAllan for golfing off 1 byte!

Try it online! or verify all test cases.

How it works

ð*Ḷ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.

Answer 4

Jelly, 12 bytes

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

TryItOnline!

Will work for any n, given enough memory, Jelly's base conversion is not restrictive.

How?

*`Ḷ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)

Answer 5

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}

Answer 6

Perl 6, 47 bytes

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

Returns a Seq. ( Seq is a basic Iterable wrapper for Iterators )

With an input of 16 it takes 20 seconds to calculate the 53905th element of the Seq (87887).

Expanded:

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

Answer 7

Batch, 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%

Won't work for n > 9 because Batch only has 32-bit arithmetic. Conveniently, Batch evaluates f &= b ^= f = 1 << j % n as f = 1 << j % n, b = b ^ f, f = f & b rather than f = f & (b = b ^ (f = 1 << j % n)).

Answer 8

Mathematica, 59 48 bytes

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

Contains U+F4A1 "Private Use" character

Explanation

Range[#^#]-1

Generate {1, 2, ..., n^n}. Subtract 1. (yields {0, 1, ..., n^n - 1})

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

A Boolean function: True if each digit occurs at most once in base n.

Select[ ... ]

From the list {0, 1, ..., n^n - 1}, select ones that give True when the above Boolean function is applied.

59 byte version

Select[Range[#^#]-1,xDuplicateFreeQ[x~IntegerDigits~#]]&

Answer 9

Mathematica, 48 55 bytes

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

(The triple space between the xs needs to be replaced by the 3-byte character \uF4A1 to make the code work.)

Unnamed function of a single argument. Rather than testing integers for xenodromicity, it simply generates all possible permutations of subsets of the allowed digits (which automatically avoids repetition) and converts the corresponding integers to base 10. Each xenodrome is generated twice, both with and without a leading 0; Union removes the duplicates and sorts the list to boot.

Answer 10

Vyxal, 7 bytes

eʁ'?τÞu

Try it Online!

 ʁ      # Range(0, 
e       # n**n
  '     # Filtered by...
   ?τ   # Convert to base n
     Þu # All unique?

Answer 11

Vyxal, 14 13 bytes

ʁṖƛÞSƛṖ⁰vβ]fU

Try it Online!

ʁṖƛÞSƛṖ⁰vβ]fU
ʁ             # Range [0, n)
 Ṗƛ       ]   # For each permutation:
   ÞSƛ        # For each sublist in the permutation:
      Ṗ         # Generate the permutations of that
        v       # For each permutation:
         β        # Treating it as a list of digits, convert to base 10 from base
       ⁰          # <the input>
           f  # Flatten the resulting list
            U # Remove duplicates

Answer 12

Haskell, 100 80 bytes

-20 bytes thanks to @Laikoni

f k=[n|n<-[0..k*k^k],let x#0=1>0;x#n|m<-mod n k=notElem m x&&(m:x)#div n k,[]#n]

Try it online!

Answer 13

Ruby, 73 bytes

->n,*a{i=-1
n>1?(0..n**n).filter_map{i+=1
d=i.digits(n)
i if d==d&d}:[0]}

Attempt This Online!

Answer 14

Japt, 14 bytes

o à cá mìU â ñ

Try it

Explanation:

o à cá mìU â ñ
o              # Get the range [0...input]
  à            # Find all arrays containing unique items from that range
    cá         # Find all orderings for each of those arrays
       m       # For each one:
         U     #  Treat it as an array of base-input digits
        ì      #  Convert it to a base-10 number
           â   # Remove duplicates
             ñ # Sort by ascending value

This alternative and this other alternative are longer, but seems like that strategy could become shorter if someone finds a better way to check for "contains no duplicate elements".

Answer 15

05AB1E, 8 bytes

mÝʒIвDÙQ

Try it online or verify all test cases.^†

Explanation:

m         # Push the (implicit) input to the power of the (implicit) input: nⁿ
 Ý        # Pop and push a list in the range [0,nⁿ]
  ʒ       # Filter this list by:
   Iв     #  Convert the integer to base-input as list
     DÙQ  #  Check if all items in this list are unique:
     D    #   Duplicate the list
      Ù   #   Uniquify the items in the copy
       Q  #   Check if the two lists are still the same
          # (after which the result is output implicitly)

† Note: input \$n=1\$ will output as [0,1] instead of [0]. This could be fixed in +1 byte by adding a ¨ after the Ý, to make the range \$[0,n^n)\$ instead. However, I'd argue for \$n=1\$ it should be allowed to output either [0] or [0,1]. If base-1 follows the same rules as the other bases, only 0 can be represented, making it practically useless. Because of that, bijective base-1 (aka unary) is usually used instead when someone talks about base-1, in which case:

1. \$n=0\$ as bijective base-1 will have an empty result (technically all unique)
2. \$n=1\$ as bijective base-1 results in a single tally mark (thus all unique)
3. \$n\geq2\$ as bijective base-1 results in \$n\$ amount of tally mark (thus not all unique)

Answer 16

Japt, 13 10 bytes

pU ÇìU'âÃâ

Try it

pU ÇìU'âÃâ     :Implicit input of integer U
pU             :Raised to the power of itself
   Ç           :Map the range [0,U**U)
    ìU         :  Convert to base U digit array
      'â       :  Deduplicate and convert back to integer
        Ã      :End map
         â     :Deduplicate