Proposing "isperm()" (user featured routine)

[R J Cano <0xccaaffee@gmail.com>]

Greetings.

Briefly,

Motivation, source code, explanation/documentation, and examples in
the attachment.

Cheers,

Remy

/* (PARI) _R. J. Cano_, May 11 2017

   isperm(n,{strict=0},{allowRep=1},{stopAt=+oo},{resumeFrom=0}); Description/Purpose:
   
      Find (if exists) the least base "beta" where n is written as a permutation for some of its digits (with/without allowing digits repetition).
  
   Note:  An "strict" search (usually also quite slower) means to search only those permutations of 0..k-1 with some k>1;
          where for some m<=k, all the first m digits enter (a leading zero, inclusive). */

isperm(n,{strict=1},{allowRep=0},{stopAt=+oo},{resumeFrom=0})={ my(theDigits:vec,tryThese:vecsmall,piano,touch,pass:small,pattern:vecsmall,leadingzero:small);
   forstep(Beta=max(2,resumeFrom),max(2,n-1),1, piano*=0*(pass=1); theDigits=digits(n,Beta); tryThese=Vecsmall(theDigits);
     for(i=1,#tryThese,
       touch=1<<tryThese[i];
       if(bitand(touch,piano),if(!allowRep,pass=0;break),piano+=touch) );
     if(pass,
       leadingzero=!(piano%2);    
       pattern=Vecsmall(vecsort(concat([0],theDigits),,8));
       if(#pattern==leadingzero+hammingweight(piano),if((strict&&(#pattern==sum(u=1,#pattern,pattern[u]==u-1)))||!strict,return(Beta))) );
     if(Beta>stopAt,return(-1)) ); /* Nothing found, incomplete search */
   return(0) } /* Nothing found, complete search */

\\ Example: 1) Strict search

\\  isperm(27,1) returns 4 since 27 = 123[4] (with/without a leading zero) 
\\  isperm(123,1) returns 10 since 123 = 123[10] (Also with/without a leading zero) 

\\ In both cases above, respectively 4, and 10 are the least bases where it is possible
\\ to represent n as a permutation, entering all the digits although leading zeros are not written.

\\  2) Non strict search:

x = 314159265358979323; \\ Some few digits borrowed from Pi.
y = isperm(x,0); \\ returns 34 for this example.
R=digits(x,y);
z=Set(concat([0],R));
t=concat(if(#R<#z,[0],[]),vector(#R,i,-1+vecsearch(z,R[i]))); \\ Appends a leading zero to complete all the digits, if required.

human=concat(vector(#t,j,Strchr(if(0<=t[j]&&t[j]<=9,48,55)+t[j]))); \\ Returns "026435A891BC7" for this example.

\\ As long as we keep stored the map (for this example, in z), we can recover x from "human". 

Dictionary(x:str)={my(data=Vec("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"));for(k=1,#data,if(x==data[k],return(k)));return(0)}; \\ By 0 here we mean: Not found.

fromHuman=fromdigits(apply(q->z[q],apply(Dictionary,Vec(human))),y);

\\ (The End?)

/* Sample execution. Output dump:
 
bash-4.3$ clear; cd ~/gp; gp2c -g isperm.txt > isperm.txt.c; gp2c-run ./isperm.txt.c 
Warning:isperm.txt:11: Assignement to a less precise type: vec<-gen
theDigits=digits(n,Beta)
Reading GPRC: /etc/gprc ...Done.

                                            GP/PARI CALCULATOR Version 2.9.2 (released)
                                    amd64 running linux (x86-64/GMP-6.1.1 kernel) 64-bit version
                                           compiled: May  6 2017, gcc version 5.3.0 (GCC)
                                                      threading engine: single
                                           (readline v6.3 enabled, extended help enabled)

                                               Copyright (C) 2000-2017 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?15 for how to get moral (and possibly technical) support.

parisizemax = 4096000000, primelimit = 10000000
(May 11 2017, 00:31 VET) gp > isperm(1231132) \\ Strict search.
time = 1min, 55,095 ms.
%1 = 1231130
(May 11 2017, 00:33 VET) gp > digits(1231132,1231130) \\ Don't forget the leading zero. Must actually be read "012"
%2 = [1, 2]
(May 11 2017, 00:33 VET) gp > 
 
*/