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

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 3

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

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 7

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 8

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 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.