Entrée: une séquence de lettres majuscules (ASCII [65; 90]) qui est la N ème * permutation lexicographique du multiset de ses caractères

* les permutations sont numérotées de 0 ou 1 vers le haut

Sortie: base 10 entier N

Rulez

• Il peut y avoir des doublons (c'est en quoi ce défi diffère de celui-ci )
• Les caractères sont classés par leur valeur ASCII
• Dans le cas d'une entrée de longueur inférieure ou égale à 1, l'entrée est la première permutation et le résultat est 0ou 1respectivement
• La première permutation est celle dans laquelle le caractère le plus à gauche a la valeur la plus basse, le caractère le plus à droite a la valeur la plus élevée, et la séquence de caractères entre le premier et le dernier caractère est la première permutation du multiset de ses caractères (définition récursive!)
• Victoires les plus courtes

Exemple

• L'entrée AABproduit la sortie0
• L'entrée ABAproduit la sortie1
• L'entrée BAAproduit la sortie2

• L'entrée ZZZproduit la sortie0
• L'entrée DCBAproduit la sortie23

ÉDITER

Bravo à celui qui peut trouver une solution qui ne produit pas toutes les permutations et rechercher ensuite l'entrée. Voilà un défi.

Gelée , 5 octets

Œ!QṢi

Essayez-le en ligne!

Sortie indexée 1.

Python 2, 69 octets

Essayez-le en ligne

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

Python, 302 287 octets

Dead Possum a déjà publié une courte solution Pythonic, j'ai donc décidé d'aller chercher les félicitations supplémentaires. Cette solution ne génère pas toutes les permutations. Il peut calculer rapidement l'indice de permutation d'une chaîne assez grande; il gère également correctement une chaîne vide.

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

Code de test:

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)

production

 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

Version non golfée:

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

Sur lexico_permute_string

Cet algorithme, dû à Narayana Pandita, provient de https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Pour produire la prochaine permutation dans l'ordre lexicographique de séquence a

1. Trouvez le plus grand indice j tel que a [j] <a [j + 1]. S'il n'existe aucun indice de ce type, la permutation est la dernière permutation.
2. Trouver le plus grand indice k supérieur à j tel que a [j] <a [k].
3. Échangez la valeur de [j] avec celle de [k].
4. Inverse la séquence de a [j + 1] jusqu'à et y compris l'élément final a [n].

FWIW, vous pouvez voir une version annotée de cette fonction ici .

FWIW, voici la fonction inverse.

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

production

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

Et voici une fonction que j'ai écrite tout en développant perm_unrankqui montre la répartition des sous-comptes.

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)

production

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 octets

œêJ¹k

Utilise l' encodage CP-1252 . Essayez-le en ligne!

05AB1E , 5 octets

œê¹Sk

Essayez-le en ligne!

Découvert indépendamment de la réponse d'Adnan.

PHP, 124 octets

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

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++);

Version en ligne

Courir avec

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

Calculer avec factorielle

Version étendue

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

Sortie pour la chaîne 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
)

Version en ligne

Julia, 121 125 octets

Non compétitif, car il ne traite pas correctement les lettres en double. J'ai porté cela à partir d'une autre langue, d'une partie d'une solution à un problème Project Euler que j'avais fait il y a plusieurs années, et la première version de 121 octets avait un bogue parce que j'avais transposé l'utilisation de la chaîne permutée et la référence canonique triée chaîne.

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)

Pour les grandes entrées, cette version utilise des bignums au prix de 8 octets supplémentaires:

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)

Non 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

Utilise un système de nombres factoriadique , qv Ainsi, il ne produit pas toutes les permutations et pour de grandes entrées, il fonctionnera énormément plus rapidement que ceux qui le font.

Par exemple, l'alphabet peut être permuté dans la phrase plutôt artificielle "Travail de glyphe de quartz vex'd cwm finks." Cette phrase est la 259.985.607.122.410.643.097.474.123ème permutation lexicographique des lettres de l'alphabet. (Environ 260 septillionième permutation.) Ce programme trouve cela dans environ 65 µs sur ma machine.

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

Notez que le nombre se termine par ... 122 plutôt que par ... 123 car OP a demandé que les permutations soient numérotées de 0 plutôt que de 1.

Julia, 375 octets

J'ai laissé l'indentation pour plus de lisibilité, mais le nombre d'octets est sans elle.

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

Celui-ci n'est qu'un simple port Julia de la brillante solution Python de PM 2Ring. J'ai eu faim, alors j'ai décidé que je voulais le cookie après tout. Il est intéressant de voir les similitudes et les différences entre les deux langues. J'ai implémenté itertools.groupby(sous une forme limitée) en tant que g(w).

Mais la logique n'est pas la mienne, alors allez voter la réponse de PM 2Ring .

Remplacez f=factorialpar f(x)=factorial(BigInt(x))si vous voulez être capable de gérer de grandes entrées comme p ("QUARTZGLYPHJOBVEXDCWMFINKS").

MATL , 13 12 11 octets

1 octet économisé grâce à GB !

tY@Xu=!Af1)

La sortie est basée sur 1.

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

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 octets

La modification de la spécification du problème a permis une économie de 2 octets.

Permutations@Sort@#~Position~#&

Fonction pure prenant une liste en entrée et retournant un entier non négatif Nsous la forme {{N}}.

JavaScript (ES6), 130 octets

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)

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

Tester

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 octets

q_e!\a#

Essayez-le en ligne!

Pyth, 5 octets

xS{.p

Interprète en ligne

Prend l'entrée citée.

Scala, 40 octets

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

Pour l'utiliser, affectez cette fonction à une variable:

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

Essayez-le en ligne sur ideone

Malheureusement, permutationsretourne un itérateur, qui n'a pas de sortedméthode, il doit donc être converti en unSeq

C ++, 96 octets

Nous pouvons utiliser pleinement la bibliothèque standard ici. La liste des lettres est transmise en tant qu'itérateurs de début / fin dans le style C ++ standard.

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

Nous n'avons pas besoin de générer toutes les permutations - puisque nous avons une transformation d'une permutation à son prédécesseur, nous comptons simplement le nombre d'itérations nécessaires pour atteindre la valeur zéro.

Programme de test:

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

Résultats de test:

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

Japt, 6 octets

0 indexé

ñ á bU

Essayez-le

Rubis, 50 octets

Je m'attendais à ce que ce soit plus court. Je n'aurais pas ajouté le sortsi les documents n'avaient pas dit "la mise en œuvre ne donne aucune garantie quant à l'ordre dans lequel les permutations sont produites".

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