Dane wejściowe: ciąg wielkich liter (ASCII [65; 90]), który jest n- tą * leksykograficzną permutacją multisettu jego znaków

* permutacje są ponumerowane od 0 lub 1 w górę

Wyjście: liczba całkowita base-10 N.

Rulez

• Mogą istnieć duplikaty (tak różni się to wyzwanie od tego )
• Znaki są uporządkowane według wartości ASCII
• W przypadku wprowadzania na długość mniejszą niż lub równą 1, sygnał wejściowy jest pierwszym permutacji i wynik 0lub 1, odpowiednio
• Pierwsza permutacja to ta, w której znak znajdujący się najbardziej po lewej stronie ma najniższą wartość, znak znajdujący się najbardziej po prawej stronie ma najwyższą wartość, a sekwencja znaków między pierwszym a ostatnim znakiem jest pierwszą permutacją multiset jego znaków (definicja rekurencyjna!)
• Zwycięża najkrótsza pozycja

Przykład

• Wejście AABwytwarza wynik0
• Wejście ABAwytwarza wynik1
• Wejście BAAwytwarza wynik2

• Wejście ZZZwytwarza wynik0
• Wejście DCBAwytwarza wynik23

EDYTOWAĆ

Dodatkowe podziękowania dla tego, który może wymyślić rozwiązanie, które nie generuje wszystkich permutacji, a następnie wyszukać dane wejściowe. To jakieś wyzwanie.

Galaretka , 5 bajtów

Œ!QṢi

Wypróbuj online!

Wyjście 1-indeksowane.

Python 2, 69 bajtów

Wypróbuj online

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

Python, 302 287 bajtów

Dead Possum opublikowało już krótkie rozwiązanie w języku Python, więc zdecydowałem się na dodatkowe wyróżnienia. To rozwiązanie nie generuje wszystkich permutacji. Może szybko obliczyć wskaźnik permutacji raczej dużego ciągu; poprawnie obsługuje również pusty ciąg.

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

Kod testowy:

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)

wynik

 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

Wersja bez gry w golfa:

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

O lexico_permute_string

Ten algorytm, dzięki Narayana Pandita, pochodzi z https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Aby utworzyć następną permutację w porządku leksykograficznym sekwencji a

1. Znajdź największy indeks j taki, że a [j] <a [j + 1]. Jeśli taki indeks nie istnieje, permutacja jest ostatnią permutacją.
2. Znajdź największy indeks k większy niż j taki, że a [j] <a [k].
3. Zamień wartość [j] na wartość [k].
4. Odwróć sekwencję od [j + 1] do ostatniego elementu włącznie [n].

FWIW można zobaczyć uwagami wersję tej funkcji tutaj .

FWIW, oto funkcja odwrotna.

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

wynik

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

A oto funkcja, którą napisałem podczas opracowywania, perm_unrankktóra pokazuje rozkład subkont.

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)

wynik

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 bajtów

œêJ¹k

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

05AB1E , 5 bajtów

œê¹Sk

Wypróbuj online!

Niezależnie odkryta z odpowiedzi Adnana.

PHP, 124 bajty

$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 bajtów

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

Wersja online

Biegnij z

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

Oblicz z silnią

Wersja rozszerzona

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

Dane wyjściowe dla ciągu 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
)

Wersja online

Julia, 121 125 bajtów

Niekonkurencyjne, ponieważ nie radzi sobie z powielonymi literami. Przeniesiłem to z innego języka, od części rozwiązania problemu Project Euler, który zrobiłem kilka lat temu, a pierwsza, 121-bajtowa wersja miała błąd, ponieważ transponowałem użycie permutowanego ciągu i posortowane, kanoniczne odniesienie strunowy.

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)

W przypadku dużych nakładów ta wersja używa bignów kosztem 8 dodatkowych bajtów:

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)

Nie golfowany:

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

Wykorzystuje system liczb czynnikowych , qv W ten sposób nie produkuje wszystkich permutacji i dla dużych danych wejściowych będzie działał znacznie szybciej niż te, które to robią.

Na przykład, alfabet można zapisać w dość wymyślonym zdaniu „Glif Quartz Job vex'd cwm finks”. To zdanie to 259.985,607,122,410,643,097,474,123 123 permutacja leksykograficzna liter alfabetu. (Około 260 septillionowych permutacji.) Ten program znajduje to w około 65 µs na mojej maszynie.

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

Zauważ, że liczba kończy się na ... 122 zamiast ... 123, ponieważ OP zażądał, aby permutacje były ponumerowane od 0 zamiast od 1.

Julia, 375 bajtów

Zostawiłem wcięcie dla czytelności, ale liczba bajtów jest bez niego.

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

Ten jest tylko prostym portem Julii genialnego rozwiązania PM 2Ring w języku Python. Byłem głodny, więc zdecydowałem, że mimo wszystko chcę ciasteczka. Ciekawie jest zobaczyć podobieństwa i różnice między dwoma językami. Zaimplementowałem itertools.groupby(w ograniczonej formie) jako g(w).

Ale logika nie jest moja, więc idź i poprzyj odpowiedź PM 2Ring .

Wymień f=factorialsię f(x)=factorial(BigInt(x)), jeśli chcesz być w stanie obsługiwać dużych nakładów jak p ( „QUARTZGLYPHJOBVEXDCWMFINKS”).

MATL , 13 12 11 bajtów

1 bajt zapisany dzięki GB !

tY@Xu=!Af1)

Wyjście jest oparte na 1.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

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 bajtów

Zmiana specyfikacji problemu pozwoliła na oszczędności 2-bajtowe.

Permutations@Sort@#~Position~#&

Czysta funkcja pobierająca listę jako dane wejściowe i zwracająca nieujemną liczbę całkowitą Nw formularzu {{N}}.

JavaScript (ES6), 130 bajtów

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)

Mniej golfa

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
}

Test

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 bajtów

q_e!\a#

Wypróbuj online!

Pyth, 5 bajtów

xS{.p

Tłumacz online

Pobiera cytowane dane wejściowe.

Scala, 40 bajtów

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

Aby z niego skorzystać, przypisz tę funkcję do zmiennej:

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

Wypróbuj online w ideone

Niestety permutationszwraca iterator, który nie ma sortedmetody, więc należy go przekonwertować naSeq

C ++, 96 bajtów

Tutaj możemy w pełni wykorzystać standardową bibliotekę. Lista liter jest przekazywana jako iteratory początkowe / końcowe w standardowym stylu C ++.

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

Nie musimy generować wszystkich permutacji - ponieważ mamy transformację z jednej permutacji do jej poprzednika, po prostu liczymy, ile iteracji potrzeba, aby osiągnąć wartość zerową.

Program testowy:

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

Wyniki testu:

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

Japt, 6 bajtów

0-indeksowane

ñ á bU

Spróbuj

Rubinowy, 50 bajtów

Spodziewałem się, że będzie to krótsze. Nie sortdodałbym, gdyby dokumenty nie mówiły „implementacja nie daje żadnych gwarancji co do kolejności uzyskiwania permutacji”.

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