De entrada: una secuencia de letras mayúsculas (ASCII [65; 90]) que es el N º * permutación lexicográfico del conjunto múltiple de sus caracteres

* las permutaciones están numeradas de 0 o 1 hacia arriba

Salida: entero de base 10 N

Rulez

• Puede haber duplicados (así es como este desafío difiere de este )
• Los caracteres están ordenados por su valor ASCII
• En el caso de una entrada de longitud menor o igual a 1, la entrada es la primera permutación y el resultado es 0o 1respectivamente
• La primera permutación es aquella en la que el carácter más a la izquierda tiene el valor más bajo, el carácter más a la derecha tiene el valor más alto y la secuencia de caracteres entre el primer y el último carácter es la primera permutación del conjunto múltiple de sus caracteres (¡definición recursiva!)
• La entrada más corta gana

Ejemplo

• La entrada AABproduce salida0
• La entrada ABAproduce salida1
• La entrada BAAproduce salida2

• La entrada ZZZproduce salida0
• La entrada DCBAproduce salida23

EDITAR

Felicitaciones adicionales a quien puede encontrar una solución que no produzca todas las permutaciones y luego busque la entrada. Eso es un reto.

Jalea , 5 bytes

Œ!QṢi

Pruébalo en línea!

Salida indexada 1.

Python 2, 69 bytes

Pruébalo en línea

from itertools import*
lambda S:sorted(set(permutations(S))).index(S)

Python, 302 287 bytes

Dead Possum ya ha publicado una solución Pythonic corta, así que decidí ir por las felicitaciones adicionales. Esta solución no genera todas las permutaciones. Puede calcular rápidamente el índice de permutación de una cadena bastante grande; También maneja una cadena vacía correctamente.

from math import factorial as f
from itertools import groupby as g
def p(t,b=''):
 if len(t)<2:return 0
 z,b=0,b or sorted(t)
 for i,c in enumerate(b):
  w=b[:i]+b[i+1:]
  if c==t[0]:return z+p(t[1:],w)
  if i<1 or c!=b[i-1]:
   n=f(len(w))
   for _,v in g(w):n//=f(len(list(v)))
   z+=n

Código de prueba:

def lexico_permute_string(s):
    ''' Generate all permutations of `s` in lexicographic order '''
    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break
        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]

def test_all(base):
    for i, s in enumerate(lexico_permute_string(base)):
        rank = p(s)
        assert rank == i, (i, s, rank)
        print('{:2} {} {:2}'.format(i, s, rank))
    print(repr(base), 'ok\n')

for base in ('AAB', 'abbbbc'):
    test_all(base)

def test(s):
    print('{!r}\n{}\n'.format(s, p(s)))

for s in ('ZZZ', 'DCBA', 'a quick brown fox jumps over the lazy dog'):
    test(s)

salida

 0 AAB  0
 1 ABA  1
 2 BAA  2
'AAB' ok

 0 abbbbc  0
 1 abbbcb  1
 2 abbcbb  2
 3 abcbbb  3
 4 acbbbb  4
 5 babbbc  5
 6 babbcb  6
 7 babcbb  7
 8 bacbbb  8
 9 bbabbc  9
10 bbabcb 10
11 bbacbb 11
12 bbbabc 12
13 bbbacb 13
14 bbbbac 14
15 bbbbca 15
16 bbbcab 16
17 bbbcba 17
18 bbcabb 18
19 bbcbab 19
20 bbcbba 20
21 bcabbb 21
22 bcbabb 22
23 bcbbab 23
24 bcbbba 24
25 cabbbb 25
26 cbabbb 26
27 cbbabb 27
28 cbbbab 28
29 cbbbba 29
'abbbbc' ok

'ZZZ'
0

'DCBA'
23

'a quick brown fox jumps over the lazy dog'
436629906477779191275460617121351796379337

Versión sin golf:

''' Determine the rank (lexicographic index) of a permutation 
    The permutation may contain repeated items

    Written by PM 2Ring 2017.04.03
'''

from math import factorial as fac
from itertools import groupby

def lexico_permute_string(s):
    ''' Generate all permutations of `s` in lexicographic order '''
    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break
        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]

def perm_count(s):
    ''' Count the total number of permutations of sorted sequence `s` '''
    n = fac(len(s))
    for _, g in groupby(s):
        n //= fac(sum(1 for u in g))
    return n

def perm_rank(target, base):
    ''' Determine the permutation rank of string `target`
        given the rank zero permutation string `base`,
        i.e., the chars in `base` are in lexicographic order.
    '''
    if len(target) < 2:
        return 0
    total = 0
    head, newtarget = target[0], target[1:]
    for i, c in enumerate(base):
        newbase = base[:i] + base[i+1:]
        if c == head:
            return total + perm_rank(newtarget, newbase)
        elif i and c == base[i-1]:
            continue
        total += perm_count(newbase)

base = 'abcccdde'
print('total number', perm_count(base))

for i, s in enumerate(lexico_permute_string(base)):
    rank = perm_rank(s, base)
    assert rank == i, (i, s, rank)
    #print('{:2} {} {:2}'.format(i, s, rank))
print('ok')

Acerca de lexico_permute_string

Este algoritmo, debido a Narayana Pandita, es de https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Para producir la próxima permutación en orden lexicográfico de secuencia a

1. Encuentre el índice más grande j tal que a [j] <a [j + 1]. Si no existe dicho índice, la permutación es la última permutación.
2. Encuentre el índice más grande k mayor que j tal que a [j] <a [k].
3. Cambie el valor de a [j] con el de a [k].
4. Invierta la secuencia desde a [j + 1] hasta e incluyendo el elemento final a [n].

FWIW, puedes ver una versión anotada de esa función aquí .

FWIW, aquí está la función inversa.

def perm_unrank(rank, base, head=''):
    ''' Determine the permutation with given rank of the 
        rank zero permutation string `base`.
    '''
    if len(base) < 2:
        return head + ''.join(base)

    total = 0
    for i, c in enumerate(base):
        if i < 1 or c != base[i-1]:
            newbase = base[:i] + base[i+1:]
            newtotal = total + perm_count(newbase)
            if newtotal > rank:
                return perm_unrank(rank - total, newbase, head + c)
            total = newtotal
# Test

target = 'a quick brown fox jumps over the lazy dog'
base = ''.join(sorted(target))
rank = perm_rank(target, base)
print(target)
print(base)
print(rank)
print(perm_unrank(rank, base))

salida

a quick brown fox jumps over the lazy dog
        aabcdeefghijklmnoooopqrrstuuvwxyz
436629906477779191275460617121351796379337
a quick brown fox jumps over the lazy dog

Y aquí hay una función que escribí durante el desarrollo perm_unrankque muestra el desglose de los subcontes.

def counts(base):
    for i, c in enumerate(base):
        newbase = base[:i] + base[i+1:]
        if newbase and (i < 1 or c != base[i-1]):
            yield c, perm_count(newbase)
            for h, k in counts(newbase):
                yield c + h, k 

def show_counts(base):
    TAB = ' ' * 4
    for s, t in counts(base):
        d = len(s) - 1
        print('{}{} {}'.format(TAB * d, s, t))

# Test
base = 'abccc'
print('total number', perm_count(base))
show_counts(base)

salida

a 4
    ab 1
        abc 1
            abcc 1
    ac 3
        acb 1
            acbc 1
        acc 2
            accb 1
            accc 1
b 4
    ba 1
        bac 1
            bacc 1
    bc 3
        bca 1
            bcac 1
        bcc 2
            bcca 1
            bccc 1
c 12
    ca 3
        cab 1
            cabc 1
        cac 2
            cacb 1
            cacc 1
    cb 3
        cba 1
            cbac 1
        cbc 2
            cbca 1
            cbcc 1
    cc 6
        cca 2
            ccab 1
            ccac 1
        ccb 2
            ccba 1
            ccbc 1
        ccc 2
            ccca 1
            cccb 1

05AB1E , 5 bytes

œêJ¹k

Utiliza la codificación CP-1252 . Pruébalo en línea!

05AB1E , 5 bytes

œê¹Sk

Pruébalo en línea!

Descubierto independientemente de la respuesta de Adnan.

PHP, 124 bytes

$a=str_split($argn);sort($a);for($i=$j=join($a);$i<=strrev($j);$i++)$i==$argn?print+$n:(($c=count_chars)($i)!=$c($j)?:$n++);

PHP, 136 bytes

foreach($t=($c=count_chars)($argn)as$k=>$v)$i=$s.=str_repeat(chr($k),$v);for(;$i<=strrev($s);$i++)$i==$argn?print+$n:($c($i)!=$t?:$n++);

Versión en línea

Corre con

echo '<string>' | php -nR '<code>'

Calcular con factorial

Versión ampliada

function f($i){return array_product(range(1,$i));} #factorial
function p($s){
return f(strlen($s))/array_product(array_map("f",count_chars($s,1)));
} # factorial / divide through product of factorials for each char
$a=$argn;
$b="";
$r=[];
for($d=0;$a;$d++) # loop range before used chars in string 
{
    for($i=0;$i<strlen($a);$i++){ # loop for every char in the rest string 
        if($a[$i]<$a[0]) # if char is before first char order by ascii
        $r[$d.$a[$i]]=p(substr_replace($a,"",$i,1)); # add range before
    }
    $a=substr($a,1); # remove first char
}
echo array_sum($r); # Output the range before the used permutation

Salida para la cadena PPCG

Array
(
    [0C] => 3    # in first run C is before P startposition = 3
    [0G] => 3    # in first run G is before P startposition = 3+3
    [1C] => 2    # in second run PC is before PP startposition = 3+3+2
    [1G] => 2    # in second run PG is before PP startposition = 3+3+2+2=8
)

Versión en línea

Julia, 121 bytes

Sin competencia, ya que no trata con letras duplicadas correctamente. Lo porté desde otro idioma, desde parte de una solución a un problema del Proyecto Euler que hice hace varios años, y la primera versión de 121 bytes tenía un error porque había transpuesto el uso de la cadena permutada y la referencia canónica ordenada cuerda.

f(p)=(n=0;z=length(p)-1;s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n)

Para entradas grandes, esta versión usa bignums a un costo de 8 bytes adicionales:

f(p)=(n=0;z=BigInt(length(p)-1);s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n)

Sin golf:

function f(perm)
    nth = 0
    size = length(perm) - 1
    sorted = join(sort(collect(p)))
    for ch in sorted
        index = search(perm, ch) - 1
        nth += factorial(size) * index
        perm = replace(perm, ch, "" , 1) # replace at most one copy
        size -= 1
    end
    return nth
end

Utiliza un sistema de numeración factorial , qv Por lo tanto, no produce todas las permutaciones y para entradas grandes se ejecutará enormemente más rápido que las que lo hacen.

Por ejemplo, el alfabeto se puede permutar en la oración más bien artificial "Trabajo de glifo de cuarzo vex'd cwm finks". Esa frase es la 259,985,607,122,410,643,097,474,123 permutación lexicográfica de las letras del alfabeto. (Aproximadamente 260 septillonésima permutación). Este programa encuentra eso en aproximadamente 65 µs en mi máquina.

julia> @time f("quartzglyphjobvexdcwmfinks")
  0.000065 seconds (570 allocations: 19.234 KB)
259985607122410643097474122

Tenga en cuenta que el número termina en ... 122 en lugar de ... 123 porque OP solicitó que las permutaciones se numeren desde 0 en lugar de desde 1.

Julia, 375 bytes

He dejado la sangría para facilitar la lectura, pero el recuento de bytes está sin ella.

p(t,b="")=begin
    l=length
    if l(t)<2 return 0 end
    f=factorial
    g(w)=(a=[];
        while w!=""
            s=""
            for c in w if c==w[1] s="$s$c" end end
            w=replace(w,s,"")
            push!(a,s)
        end;a)
    b=b>""?b:join(sort(collect(t)))
    z=0
    for(i,c) in enumerate(b)
        w=b[1:i-1]*b[i+1:end]
        if c==t[1] return z+p(t[2:end],w)
        elseif i>1&&c==b[i-1] continue end
        n=f(l(w))
        for v in g(w) n=div(n,f(l(v))) end
        z+=n
    end
    z
end

Este es solo un puerto directo de Julia de la brillante solución Python de PM 2Ring. Tenía hambre, así que decidí que quería la galleta después de todo. Es interesante ver las similitudes y las diferencias entre los dos idiomas. Implementéitertools.groupby (de forma limitada) como g(w).

Pero la lógica no es mía, así que vota la respuesta de PM 2Ring .

Reemplace f=factorialcon f(x)=factorial(BigInt(x))si desea poder manejar entradas grandes como p ("QUARTZGLYPHJOBVEXDCWMFINKS").

MATL , 13 12 11 bytes

¡1 byte guardado gracias a GB !

tY@Xu=!Af1)

La salida está basada en 1.

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

Explicación

t      % Input string implicitly. Duplicate
Y@     % All permutations, sorted; each in a different row
Xu     % Unique rows
=      % Compare for equality, with broadcast
!      % Transpose
A      % All: true for columns that contain all entries true
f      % Find: indices of nonzero elements
1)     % Get first of those indices. Implicitly display

Mathematica, 33 31 bytes

Cambiar la especificación del problema permitió un ahorro de 2 bytes.

Permutations@Sort@#~Position~#&

Función pura que toma una lista como entrada y devuelve un entero no negativo Nen el formulario {{N}}.

JavaScript (ES6), 130 bytes

s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||o.add(q.join``))([...s],[])&&[...o].sort().indexOf(s)

Menos golf

s=>{
  o = new Set; // use a set to avoid duplicates

  // recursive function to build all permutations (no cookie for me)
  p = (s, q) => 
  {
    y = s.map( (t,i) => // execute for each char at position i
          (
             t = [...s], // using t as local variable, store a copy of s
             x = t.splice(i,1), // remove char from t in position i, and store in array x
             p(t, q.concat(x)) // recursive call
          ));
    if (!y[0]) // if s was empty, I have a new permutation in q
      o.add( q.join('')) // convert to string and add to output set 
  }
  // call p to enumerate all permutations
  p( [...s], [] ) // convert string s to array, q starts empty

  o = [...o].sort() // get elements of o and sort lexicographically 
  return o.indexOf(s) // return the position of the input in o
}

Prueba

F=
s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||o.add(q.join``))([...s],[])&&[...o].sort().indexOf(s)

function update() {
  O.textContent = F(I.value)
}

update()

<input id=I value='DCBA' oninput='update()'>
<pre id=O></pre>

CJam , 7 bytes

q_e!\a#

Pruébalo en línea!

Pyth, 5 bytes

xS{.p

Intérprete en línea

Toma la entrada citada.

Scala, 40 bytes

s=>s.permutations.toSeq.sorted indexOf s

Para usarlo, asigne esta función a una variable:

val f:(String=>Int)=s=>s.permutations.toSeq.sorted indexOf s
println(f("BAA"))

Pruébelo en línea en ideone

Desafortunadamente, permutationsdevuelve un iterador, que no tiene un sortedmétodo, por lo que debe convertirse en unSeq

C ++, 96 bytes

Podemos hacer un uso completo de la biblioteca estándar aquí. La lista de letras se pasa como iteradores de inicio / fin en el estilo estándar de C ++.

#include<algorithm>
int f(char*a,char*z){int i=0;while(std::prev_permutation(a,z))++i;return i;}

No necesitamos generar todas las permutaciones, ya que tenemos una transformación de una permutación a su predecesora, simplemente contamos cuántas iteraciones se necesitan para alcanzar el valor cero.

Programa de prueba:

#include<cstring>
#include<iostream>
int main(int argc, char **argv)
{
    while (*++argv)
        std::cout << *argv << ": "
                  << f(*argv, *argv+std::strlen(*argv)) << std::endl;
}

Resultados de la prueba:

BAA: 0
BAA: 1
BAA: 2
ZZZ: 0
DCBA: 23
: 0

Japt, 6 bytes

0 indexado

ñ á bU

Intentalo

Ruby, 50 bytes.

Esperaba que esto fuera más corto. No habría agregado el sortsi los documentos no dijeran "la implementación no garantiza el orden en que se producen las permutaciones".

->x{x.chars.permutation.map{|v|v*""}.sort.index x}