# Permutapalindromic numbers

Given an integer N as input, output the Nth permutapalindromic number.

A permutapalindromic number is a strictly positive integer such that there is at least one permutation of its digits that results in a palindrome (i.e. a number that is its own reverse).

For example, 117 is a permutapalindromic number since its digits can be permuted into 171, which is a palindrome.

We consider that numbers like 10 are not permutapalindromic numbers, even though 01 = 1 is a palindrome. We impose that the palindromic permutation must not have a leading zero (as such, 0 itself is not permutapalindromic).

Numbers that are already palindromes are also permutapalindromic, since permuting nothing is valid.

### Inputs and outputs

• N may be either 0-indexed or 1-indexed. Please indicate which of the two your answer uses.
• The input can be taken through STDIN, as a function argument, or anything similar in your language of choice. The output can be written to STDOUT, returned from a function, or anything similar in your language of choice.
• The input and output must be in the decimal base.

### Test cases

The following test cases are 1-indexed. Your program must be able to pass any of the test cases presented here in at most 1 minute.

N      Output

1      1
2      2
3      3
4      4
5      5
6      6
7      7
8      8
9      9
10     11
42     181
100    404
128    511
256    994
270    1166


### Scoring

This is , so the shortest answer in bytes wins.

• It's quite impossible to not pass the last testcase in one minute... Aug 17 '16 at 7:41
• OEIS A084050 (contains extra cases like 10) Aug 17 '16 at 7:44
• What is the largest input?
Aug 17 '16 at 9:01
• @Adám Your program should theoretically work for any number, no matter how big. Aug 17 '16 at 9:03
• @Adám This is a pretty arbitrary limit that is dependant on the language used. Let's say that it should theoretically work for the biggest integer your language can represent by default (so all integers if bignums is the default in your language). Aug 17 '16 at 9:11

# 05AB1E, 1514 13 bytes

Saved a byte thanks to Emigna! Code:

µNœvyJÂïÊP}_½


Explanation:

µ               # c = 0, when c is equal to the input, print N.
N              # Push N, the iteration variable.
œ             # Push all permutations of N.
vyJ    }     # For each permutation...
Â         #   Bifurcate, which is short for duplicate and reverse.
ï        #   Convert the seconds one to int, removing leading zeros.
Q       #   Check if they are not equal.
P      #   Product of the stack.
_    # Logical not.
½   # Pop a value, if 1 then increase c by 1.


Uses the CP-1252 encoding. Try it online!.

• µNœvyJÂïQ}O__½ for 14. Aug 17 '16 at 9:14
• @Emigna Thanks! I didn't think of that. Aug 17 '16 at 9:18

# Brachylog, 19 bytes

~l<:1at.
.=pPrPl~l?


Try it online!

Takes about 17 seconds for N = 270.

### Explanation

• Main predicate:

~l            Create a list whose length is Input.
<           The list is strictly increasing.
:1a        Apply predicate 1 to each element of the list.
t.      Output is the last element of the list.

• Predicate 1:

.=            Input = Output = an integer
pPrP        A permutation P of the Output is its own reverse
l~l?    The length of P is equal to the length of the Input


## Pyth, 14

e.ff&_ITshT.p


Try it here or run a Test Suite

### Expansion:

e.ff&_ITshT.pZQ   # Auto-fill variables
.f            Q   # Find the first input number of numbers that give truthy on ...
.pZ    # Take all the permutations of the current number
f&              # Keep those that give a truthy value for both:
_IT           # Invariance on reversing (is a palindrome)
shT        # The integer value of the first digit (doesn't start with zero)
# A list with any values in it it truthy, so if any permutation matches
# these conditions, the number was a permutapalindrome
e                  # Take only the last number


# Brachylog, 21 20 bytes

1 byte thanks to Fatalize.

Did you design the challenge for Brachylog?

:1yt.
0<.={@epcPrP!}


Try it online!

270 takes about half a minute here.

Z = 1166
real    0m27.066s
user    0m26.983s
sys     0m0.030s

Exit code:     0


### Predicate 0 (main predicate)

:1yt.
:1y    find the first Input solutions to predicate 1
t.  unify the output with the last element


### Predicate 1 (auxiliary predicate)

0<.={@epcPrP!}
0<.              0 < Output
.=             Assign a value to Output (choice point)
{        }   Inline predicate:
@e              Digits of the Output
p             A permutation (choice point)
c            Concatenate (fails if leading zero present)
P           store as P
rP         assert that P reversed is still P
!        remove the choice point in this predicate, so
that it will not return twice for the same number.


## JavaScript (ES6), 99 bytes

f=(n,i=1)=>(n-=/^.0+$/.test(i)</^((.),\2,)*(.)(,\3)?(,(.),\6)*$/.test([...i+''].sort()))?f(n,i+1):i


Explanation:

f=(n,i=1)=>             look for n numbers starting at 1
(n-=                   test whether current guess is
/^.0+$/.test(i)< not a round number and /^((.),\2,)* pairs of comma-separated digits (.)(,\3)? possible single digit (,(.),\6)*$/         pairs of comma-separated digits
.test(               matches the comma-joined
[...i+''].sort()))  digits in ascending order
?f(n,i+1)              if not n numbers found try next number
:i                     found it!

• 1100 is a round permutapalindromic number.
Aug 17 '16 at 9:40
• @Adám It's not round, it contains at least two nonzero digits.
– Neil
Aug 17 '16 at 9:46
• @Neil: +2 bytes -- you really ought to count the f= when you refer to it later Aug 17 '16 at 17:24
• @charlie Sorry, I always forget to do that.
– Neil
Aug 17 '16 at 17:30

# R, 145 bytes

g=function(n){d=b=0
while(d<n){b=b+1
if(sum(a<-table(strsplit(n<-as.character(b),""))%%2)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1))d=d+1}
b}


ungolfed

f=function(b){
a<-table(strsplit(n<-as.character(b),""))%%2
sum(a)==nchar(n)%%2&(!names(a)[1]==0|a[1]|sum(!a)>1)
}
g=function(n){
d=b=0
while(d<n){
b=b+a
if(f(b)) d=d+1
}
b
}


Essentially -- a function checking membership in permutapalindromic set, and a while loop incrementing until it finds the nth member.

# Python 2.7, 163 154 bytes:

from itertools import*;I,F,Q=input(),[],2
while len(F)<I:F=[g for g in range(1,Q)if any(i==i[::-1]*(i[0]>'0')for i in permutations(g))];Q+=1
print F[-1]


Simple enough. Basically uses a while loop to repeatedly create arrays containing permutapalindromic numbers the the range [1,Q) until Q is large enough such that the array contains Input number of items. It then outputs the last element in that array.

Try It Online! (Ideone)

# Perl 6, 66 bytes

{(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]}  0 based ## Explanation: # bare block lambda which takes an implicit parameter ｢$_｣
{
# all numbers greater than 0
(1..*)\

# remove any which aren't permutapalindromic
.grep(

# ｢*｣ here starts a Whatever lambda
*\
# split into list of digits
.comb\
# get all of the permutations of the digits
.permutations\
# find out if there are any palindromes
.grep(

# another bare block lambda taking ｢$_｣ as implicit parameter { # compare the current permutation with its reverse stringwise # numify only one side to get rid of leading ｢0｣ +$_.join.flip eq $_.join } ) # get the value at the index )[$_]
}


## Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &permutapalindromic = {(1..*).grep(*.comb.permutations.grep({+.join.flip eq.join}))[$_]} my @tests = ( 1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5, 6 => 6, 7 => 7, 8 => 8, 9 => 9, 10 => 11, 42 => 181, 100 => 404, 128 => 511, 256 => 994, 270 => 1166, ); plan +@tests + 1; my$start-time = now;
for @tests -> $_ ( :key($input), :value($expected) ) { # zero based instead of one based, so subtract 1 is-deeply permutapalindromic($input - 1 ), $expected, .gist; } my$finish-time = now;

my $total-time =$finish-time - $start-time; cmp-ok$total-time, &[<], 60, 'Less than 60 seconds for the tests';
diag "$total-time seconds";  # Dyalog APL, 51 bytes One-indexed. {⍵⊃{⍵/⍨{(⍵≤9)∨(1<≢c~'0')∧1≥+/2|+⌿c∘.=∪c←⍕⍵}¨⍵}⍳5×⍵}  { a function where ⍵ represents the argument ⍵⊃{ use the argument to pick from the result of the function ⍵/⍨{ filter the argument with the result of the function (⍵≤9)∨ the argument is less or equal to 9, OR (1<≢c~'0')∧ there remains more than one digit when zeros are removed AND 1≥+/ 0 or 1 is the sum of 2| the oddnesses of +⌿ of the column sums of c∘.=∪c the comparison table of c and the unique elements of c, where c... ←⍕⍵ is the string representation of the argument }¨⍵ applied to each of the arguments }⍳5×⍵ applied to {1, 2, 3, ..., 5 times the argument} } [end of function] Finishes all the test cases instantly on TryAPL • Can you prove that a(n) <= 5n? Aug 17 '16 at 8:25 • The second solution generates incorrect results. Aug 17 '16 at 8:31 • The first solution also generates incorrect results. Aug 17 '16 at 8:32 • @LeakyNun Which ones are incorrect? And if 5× isn't enough, there's space for 9×... – Adám Aug 17 '16 at 8:38 • The problem is not whether 5n is enough for the testcase. The problem is whether you can prove it. Aug 17 '16 at 8:49 # JavaScript (ES6), 92 n=>eval("for(a=0;n-=(a++<9||(b=[...a+].sort().join)>9&!b.replace(/(.)\\1/g,)[1]););a")  Less golfed n=>{ for( a = 0; n -= // decrement n (and exit when 0) if the check below is true == a is permutapalindromic (a ++ < 9 // single digit (meanwhile, increment a) || // or... ( b=[...a+].sort().join )// build a string with the digits sorted > 9 // required at least 2 non zero digits & ! b.replace(/(.)\1/g,)[1] // removed all digits pair, there must be just 1 or no single digits remaining ); ); return a; }  Test f=n=>eval("for(a=0;n-=(a++<9||(b=[...a+].sort().join)>9&!b.replace(/(.)\\1/g,)[1]););a") function update() { O.textContent=f(+I.value) } update() <input id=I oninput=update() type=number value=100> <pre id=O></pre> # Javascript (using external library - Enumerable) (142 bytes)  n=>_.Sequence(n,i=>{l=i+"";p=_.Permutations(_.From(l),l.length).Any(y=>y.First()!="0"&&y.SequenceEqual(y.Reverse()));if(p){return i;}}).Last()  Link to lib:https://github.com/mvegh1/Enumerable/ Code explanation: _.Sequence creates an enumerable for a count of "n" elements, based on the predicate of signature ("i"teration,"a"ccumulated array). Cast the current iteration to a string, and create an enumerable of all permutations from it. Test if any of the permutations satisfy the test of not starting with "0" and that the reversal of the permutation equals the permutation. Return the last element in the sequence because that is the desired output as per OP ## Python 2, 93 bytes S=sorted f=lambda n,i=1:n and-~f(n-(S(i)in[S(k)for k in range(9*i)ifk==k[::-1]]),i+1)  1-indexed. Depending on your system, the last test case may exceed the allowed recursion depth. Does not compute permutations. Instead, uses the fact that two strings are permutations if they are equal when sorted. To test if a number is permutapalindromic, checks if its sorted digits equal the sorted digits of any palindrome up to a bound. 96 bytes: f=lambda n,i=1:n and-~f(n-(sum(i.count(d)%2for d in range(10))<2*(set(i[1:])!={'0'})),i+1)  1-indexed. Depending on your system, the last test case may exceed the allowed recursion depth. This doesn't look at permutations and instead uses the following characterization: A number is permutapalindromic exactly when • At most one of its digits appears an odd number of times, and • It does not have the form d00...00 with one or more zeroes. This is true because a palindrome must pair off digits from the start and end, except for a possible center digit. The exception comes from the requirement that the leading digit be nonzero, and so some nonzero digit must appear twice unless the number is single-digit. # Haskell, 89 87 bytes import Data.List (filter(any(show.floor.read.reverse>>=(==)).permutations.show)[0..]!!)  # Jelly, 14 bytes 1DŒ!ŒḂ×ḢƊ€ẸƲ#Ṫ  Try it online! ## How it works 1DŒ!ŒḂ×ḢƊ€ẸƲ#Ṫ - Main link. Takes an argument n on the left Ʋ - Group the previous 4 links into a monad f(k): D - Convert k to digits Œ! - Permutations of k's digits Ɗ€ - Over each permutation p: ŒḂ - Is p a palindrome? ×Ḣ - And is the first digit non-zero? Ẹ - Is that true for any permutation? 1 # - Count up k = 1, 2, 3, ... until n k return true under f(k) Return those k Ṫ - Return the n'th k  # Brachylog v2, 16 bytes <~l<₁{≜.pX↔Xp}ᵐt  Try it online! Borrows Fatalize's ~l trick because my attempt at a ᵘ-based solution is a bit too slow... < The input is less than ~l the length of some list <₁ which is strictly increasing { }ᵐ where each element: ≜. is an integer chosen such that pX some permutation X ↔X is X reversed, p a permutation of which is the element. t Output the final element of that list.  # Perl 5-p, 69 bytes 1while$_-=(join'',sort++$\=~/./g)=~s/(.)\1//gr=~y///c<2*$\!~/^.0+\$/}{


Try it online!

C, 254 bytes

#define W while
#define R return
f(j){int c=0,a[16]={0};do++a[j%10],++c;W(j/=10);if(c>1&&a[0]>=c-1)R 0;c%=2;W(j<10)if(a[j++]%2&&(!c||++c>2))R 0;R 1;}g(n){int k=0,i=1;W(k<n)if(f(i++))++k;R i-1;}main(a){printf("N>");scanf("%d",&a);printf("%d\n",g(a));}
`