Eingabe: Eine Folge von Großbuchstaben (ASCII [65; 90]), die die N- te * lexikographische Permutation des Mehrfachsatzes seiner Zeichen darstellt

* Permutationen werden von 0 oder 1 aufwärts nummeriert

Ausgabe: Basis-10-Ganzzahl N

Rulez

• Es könnte Duplikate geben (so unterscheidet sich diese Herausforderung von dieser )
• Die Zeichen werden nach ihrem ASCII-Wert sortiert
• Im Fall einer Eingabe einer Länge von weniger als oder gleich 1 ist , ist der Eingang die erste Permutation und das Ergebnis ist , 0oder 1jeweils
• Die erste Permutation ist diejenige, bei der das am weitesten links stehende Zeichen den niedrigsten Wert hat, das am weitesten rechts stehende Zeichen den höchsten Wert hat und die Zeichenfolge zwischen dem ersten und dem letzten Zeichen die erste Permutation des Mehrfachsatzes seiner Zeichen ist (rekursive Definition!)
• Der kürzeste Eintrag gewinnt

Beispiel

• Input AABerzeugt Output0
• Input ABAerzeugt Output1
• Input BAAerzeugt Output2

• Input ZZZerzeugt Output0
• Input DCBAerzeugt Output23

BEARBEITEN

Zusätzliches Lob an denjenigen, der eine Lösung finden kann, die nicht alle Permutationen erzeugt und dann nach der Eingabe sucht. Das ist eine Herausforderung.

Gelee , 5 Bytes

Œ!QṢi

Probieren Sie es online!

1-indizierte Ausgabe.

Python 2, 69 Bytes

Probieren Sie es online aus

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

Python, 302 287 Bytes

Dead Possum hat bereits eine kurze Pythonic-Lösung veröffentlicht, daher habe ich mich für das besondere Lob entschieden. Diese Lösung generiert nicht alle Permutationen. Es kann den Permutationsindex einer ziemlich großen Zeichenfolge schnell berechnen. Es behandelt auch eine leere Zeichenfolge korrekt.

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

Testcode:

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)

Ausgabe

 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

Nicht Golf Version:

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

Über lexico_permute_string

Dieser Algorithmus stammt aufgrund von Narayana Pandita von https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Erzeugen der nächsten Permutation in lexikographischer Reihenfolge a

1. Finden Sie den größten Index j so, dass a [j] <a [j + 1] ist. Wenn kein solcher Index vorhanden ist, ist die Permutation die letzte Permutation.
2. Finden Sie den größten Index k größer als j, so dass a [j] <a [k] ist.
3. Tauschen Sie den Wert von a [j] mit dem von a [k].
4. Kehren Sie die Reihenfolge von a [j + 1] bis einschließlich des letzten Elements a [n] um.

FWIW, Sie können hier eine kommentierte Version dieser Funktion sehen .

FWIW, hier ist die Umkehrfunktion.

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

Ausgabe

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

Und hier ist eine Funktion, die ich während der Entwicklung geschrieben habe und perm_unrankdie die Aufteilung der Unterzählungen zeigt.

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)

Ausgabe

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

Verwendet die CP-1252- Codierung. Probieren Sie es online!

05AB1E , 5 Bytes

œê¹Sk

Probieren Sie es online!

Unabhängig von Adnans Antwort entdeckt.

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

Online Version

Laufen Sie mit

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

Mit Fakultät berechnen

Erweiterte Version

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

Ausgabe für den String 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
)

Online Version

Julia, 121 125 Bytes

Nicht konkurrierend, da doppelte Buchstaben nicht korrekt behandelt werden. Ich habe dies aus einer anderen Sprache portiert, aus einem Teil einer Lösung für ein Projekt-Euler-Problem, das ich vor einigen Jahren durchgeführt habe, und die erste 121-Byte-Version hatte einen Fehler, weil ich die Verwendung der permutierten Zeichenfolge und der sortierten kanonischen Referenz transponiert hatte Zeichenfolge.

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)

Für große Eingaben verwendet diese Version Bignums zum Preis von 8 zusätzlichen Bytes:

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

Verwendet ein faktoriadisches Zahlensystem , s. Dazu: Es werden nicht alle Permutationen erzeugt, und bei großen Eingaben wird es enorm schneller ausgeführt als bei denjenigen, die dies tun.

Zum Beispiel kann das Alphabet in den eher erfundenen Satz "Quarz-Glyphen-Job vex'd cwm finks" permutiert werden. Dieser Satz ist die 259.985.607.122.410.643.097.474.123. Lexikografische Permutation der Buchstaben des Alphabets. (Ungefähr 260 Septillionstel Permutation.) Dieses Programm findet das in ungefähr 65 µs auf meiner Maschine.

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

Beachten Sie, dass die Nummer auf ... 122 anstatt auf ... 123 endet, da OP die Nummerierung der Permutationen von 0 anstatt von 1 verlangt hat.

Julia, 375 Bytes

Ich habe die Einrückung für die Lesbarkeit belassen, aber die Byteanzahl ist ohne.

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

Dies ist nur eine reine Julia-Portierung von PM 2Rings brillanter Python-Lösung. Ich hatte Hunger und entschied, dass ich den Keks doch haben wollte. Es ist interessant, die Ähnlichkeiten und Unterschiede zwischen den beiden Sprachen zu sehen. Ich habe itertools.groupby(in eingeschränkter Form) implementiert als g(w).

Aber die Logik ist nicht meine, also stimme der Antwort von PM 2Ring zu .

Ersetzen Sie f=factorialdurch, f(x)=factorial(BigInt(x))wenn Sie in der Lage sein möchten, große Eingaben wie p ("QUARTZGLYPHJOBVEXDCWMFINKS") zu verarbeiten.

MATL , 13 12 11 Bytes

1 Byte gespart dank GB !

tY@Xu=!Af1)

Die Ausgabe ist 1-basiert.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

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

Durch Ändern der Problemspezifikation konnten 2 Byte eingespart werden.

Permutations@Sort@#~Position~#&

Reine Funktion, die eine Liste als Eingabe nimmt und eine nicht negative Ganzzahl Nim Formular zurückgibt {{N}}.

JavaScript (ES6), 130 Byte

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)

Weniger golfen

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
}

Prüfung

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#

Probieren Sie es online!

Pyth, 5 Bytes

xS{.p

Online-Dolmetscher

Übernimmt die angegebenen Eingaben.

Scala, 40 Bytes

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

Um es zu verwenden, weisen Sie diese Funktion einer Variablen zu:

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

Probieren Sie es online bei ideone

Leider wird permutationsein Iterator zurückgegeben, der keine sortedMethode hat, sodass er in eine konvertiert werden mussSeq

C ++, 96 Bytes

Hier können wir die Standardbibliothek voll ausnutzen. Die Liste der Buchstaben wird als Start- / End-Iterator im Standard-C ++ - Stil übergeben.

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

Wir müssen nicht alle Permutationen generieren - da wir eine Transformation von einer Permutation zu ihrer Vorgängerversion haben, zählen wir einfach, wie viele Iterationen erforderlich sind, um den nullten Wert zu erreichen.

Testprogramm:

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

Testergebnisse:

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

Japt, 6 Bytes

0-indiziert

ñ á bU

Versuch es

Ruby, 50 Bytes

Ich habe erwartet, dass das kürzer wird. Ich hätte das nicht hinzugefügt, sortwenn die Dokumentation nicht gesagt hätte: "Die Implementierung gibt keine Garantie für die Reihenfolge, in der die Permutationen ausgegeben werden."

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