Entrada: uma sequência de letras maiúsculas (ASCII [65; 90]), que é o N th * permutação léxicografica do multiconjunto dos seus caracteres

* permutações são numeradas de 0 ou 1 para cima

Saída: base-10 inteiro N

Rulez

• Pode haver duplicatas (é assim que este desafio difere deste )
• Os caracteres são ordenados pelo seu valor ASCII
• No caso de uma entrada de comprimento menor ou igual a 1, a entrada é a primeira permutação e o resultado é 0ou 1respectivamente
• A primeira permutação é aquela em que o caractere mais à esquerda tem o valor mais baixo, o caractere mais à direita tem o valor mais alto, e a sequência de caracteres entre o primeiro e o último caractere é a primeira permutação do multiset de seus caracteres (definição recursiva!)
• Menor entrada ganha

Exemplo

• Entrada AABproduz saída0
• Entrada ABAproduz saída1
• Entrada BAAproduz saída2

• Entrada ZZZproduz saída0
• Entrada DCBAproduz saída23

EDITAR

Parabéns extra para quem pode encontrar uma solução que não produz todas as permutações e depois procurar a entrada. Isso é um desafio.

Gelatina , 5 bytes

Œ!QṢi

Experimente online!

Saída indexada em 1.

Python 2, 69 bytes

Experimente online

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

Python, 302 287 bytes

O Dead Possum já publicou uma solução Pythonic curta, então eu decidi ir para os elogios extras. Esta solução não gera todas as permutações. Ele pode calcular rapidamente o índice de permutação de uma string bastante grande; Ele também lida com uma string vazia corretamente.

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

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)

saída

 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

Versão sem golfe:

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

Sobre lexico_permute_string

Esse algoritmo, devido a Narayana Pandita, é de https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Para produzir a próxima permutação em ordem lexicográfica de sequência a

1. Encontre o maior índice j de modo que a [j] <a [j + 1]. Se esse índice não existir, a permutação é a última permutação.
2. Encontre o maior índice k maior que j, de modo que a [j] <a [k].
3. Troque o valor de a [j] pelo valor de [k].
4. Inverta a sequência de um [j + 1] até e incluindo o elemento final a [n].

FWIW, você pode ver uma versão anotada dessa função aqui .

FWIW, aqui está a função 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))

saída

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

E aqui está uma função que escrevi durante o desenvolvimento perm_unrankque mostra a divisão das subcontas.

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)

saída

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

Usa a codificação CP-1252 . Experimente online!

05AB1E , 5 bytes

œê¹Sk

Experimente online!

Descoberto independentemente da resposta 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++);

Versão Online

Correr com

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

Calcular com fatorial

Versão expandida

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

Saída para a cadeia 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
)

Versão Online

Julia, 121 125 bytes

Não-competitivo, pois não lida com letras duplicadas corretamente. Transferi isso de outro idioma, de parte de uma solução para um problema do Project Euler que fiz vários anos atrás, e a primeira versão de 121 bytes teve um bug porque havia transposto o uso da string permutada e da referência canônica classificada corda.

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 versão usa bignums ao custo de 8 bytes extras:

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)

Ungolfed:

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 um sistema numérico fatorial , qv Portanto, ele não produz todas as permutações e, para grandes entradas, será muito mais rápido do que as que produzem.

Por exemplo, o alfabeto pode ser permutado na sentença artificial "Quartzo glifo trabalho vex'd cwm finks". Essa frase é a 259.985.607.122.410.643.097.474.123ª permutação lexicográfica das letras do alfabeto. (Aproximadamente 260 septilhionésimos permutações.) Este programa encontra isso em cerca de 65 µs na minha máquina.

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

Observe que o número termina em ... 122 em vez de ... 123 porque OP solicitou que as permutações fossem numeradas de 0 em vez de 1.

Julia, 375 bytes

Deixei o recuo para facilitar a leitura, mas a contagem de bytes está sem ele.

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 é apenas um porto Julia direto da brilhante solução Python do PM 2Ring. Eu estava com fome, então decidi que queria o biscoito, afinal. É interessante ver as semelhanças e as diferenças entre os dois idiomas. Eu implementei itertools.groupby(de forma limitada) como g(w).

Mas a lógica não é minha, então vá e vote na resposta da PM 2Ring .

Substitua f=factorialpor f(x)=factorial(BigInt(x))se desejar poder manipular entradas grandes como p ("QUARTZGLYPHJOBVEXDCWMFINKS").

MATL , 13 12 11 bytes

1 byte salvo graças ao GB !

tY@Xu=!Af1)

A saída é baseada em 1.

Experimente online! Ou verifique todos os casos de teste .

Explicação

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

Alterar a especificação do problema permitiu uma economia de 2 bytes.

Permutations@Sort@#~Position~#&

Função pura pegando uma lista como entrada e retornando um número inteiro não negativo Nno formulário {{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 golfe

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
}

Teste

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#

Experimente online!

Pitão, 5 bytes

xS{.p

Intérprete online

Toma entrada entre aspas.

Scala, 40 bytes

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

Para usá-lo, atribua esta função a uma variável:

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

Experimente online em ideone

Infelizmente, permutationsretorna um iterador, que não possui um sortedmétodo, portanto, ele deve ser convertido em umSeq

C ++, 96 bytes

Podemos fazer uso completo da biblioteca padrão aqui. A lista de letras é passada como iteradores de início / fim no estilo C ++ padrão.

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

Não precisamos gerar todas as permutações - já que temos uma transformação de uma permutação em seu predecessor, simplesmente contamos quantas iterações são necessárias para atingir o valor zero.

Programa de teste:

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

Resultado dos testes:

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

Japonês, 6 bytes

Indexado a 0

ñ á bU

Tente

Ruby, 50 bytes

Eu esperava que isso fosse mais curto. Eu não teria acrescentado sortse os documentos não dissessem "a implementação não garante a ordem pela qual as permutações são produzidas".

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