Input: urutan huruf besar (ASCII [65; 90]) yang merupakan permutasi leksikografis ke- N dari multiset karakternya

* permutasi diberi nomor dari 0 atau 1 ke atas

Output: basis-10 integer N

Rulez

• Mungkin ada duplikat (itulah sebabnya tantangan ini berbeda dari yang ini )
• Karakter diperintahkan oleh nilai ASCII mereka
• Dalam hal input dengan panjang kurang dari atau sama dengan 1, input adalah permutasi pertama dan hasilnya masing 0- 1masing
• Permutasi pertama adalah di mana karakter paling kiri memiliki nilai terendah, karakter paling kanan memiliki nilai tertinggi, dan urutan karakter antara karakter pertama dan terakhir adalah permutasi pertama dari multiset karakternya (definisi rekursif!)
• Entri terpendek menang

Contoh

• Input AABmenghasilkan output0
• Input ABAmenghasilkan output1
• Input BAAmenghasilkan output2

• Input ZZZmenghasilkan output0
• Input DCBAmenghasilkan output23

EDIT

Kudos ekstra untuk orang yang dapat menemukan solusi yang tidak menghasilkan semua permutasi dan kemudian mencari input. Itu beberapa tantangan.

Jelly , 5 byte

Œ!QṢi

Cobalah online!

Output 1-diindeks.

Python 2, 69 byte

Cobalah online

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

Python, 302 287 byte

Dead Possum telah memposting solusi Pythonic pendek, jadi saya memutuskan untuk mencari pujian tambahan. Solusi ini tidak menghasilkan semua permutasi. Ini dapat dengan cepat menghitung indeks permutasi string yang agak besar; itu juga menangani string kosong dengan benar.

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

Kode pengujian:

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)

keluaran

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

Tentang lexico_permute_string

Algoritma ini, karena Narayana Pandita, berasal dari https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Untuk menghasilkan permutasi berikutnya dalam urutan leksikografis a

1. Temukan indeks terbesar j sehingga a [j] <a [j + 1]. Jika tidak ada indeks seperti itu, permutasi adalah permutasi terakhir.
2. Temukan indeks terbesar k lebih besar dari j sehingga a [j] <a [k].
3. Tukar nilai a [j] dengan nilai a [k].
4. Membalik urutan dari [j + 1] hingga dan termasuk elemen terakhir a [n].

FWIW, Anda dapat melihat versi beranotasi dari fungsi itu di sini .

FWIW, inilah fungsi terbalik.

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

keluaran

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

Dan inilah fungsi yang saya tulis saat mengembangkan perm_unrankyang menunjukkan pengelompokan sub-bagian.

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)

keluaran

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 byte

œêJ¹k

Menggunakan pengkodean CP-1252 . Cobalah online!

05AB1E , 5 byte

œê¹Sk

Cobalah online!

Ditemukan secara independen dari jawaban 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 Online

Jalankan dengan

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

Hitung dengan faktorial

Versi yang Diperluas

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

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

Versi Online

Julia, 121 125 byte

Tidak bersaing, karena tidak berurusan dengan surat duplikat dengan benar. Saya porting ini dari bahasa lain, dari bagian dari solusi untuk masalah Project Euler yang saya lakukan beberapa tahun yang lalu, dan yang pertama, versi 121-byte memiliki bug karena saya telah mengubah penggunaan string yang di-permutasi dan referensi kanonik yang diurutkan dan diurutkan. tali.

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)

Untuk input besar, versi ini menggunakan bignum dengan biaya 8 byte tambahan:

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)

Tidak Terkumpul:

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

Menggunakan sistem angka factoriadic , qv Jadi, itu tidak menghasilkan semua permutasi dan untuk input besar akan berjalan jauh lebih cepat daripada yang melakukannya.

Sebagai contoh, alfabet dapat diubah menjadi kalimat yang agak dibuat-buat, "Pekerjaan mesin pencari kuarsa yang membuat cemas." Kalimat itu adalah 259.985.607.122.410.643.097.474.123 permutasi leksikografis dari huruf-huruf alfabet. (Kira-kira 260 septillionth permutasi.) Program ini menemukan bahwa sekitar 65 μs pada mesin saya.

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

Perhatikan bahwa nomor berakhir pada ... 122 daripada ... 123 karena OP meminta agar permutasi diberi nomor dari 0 daripada dari 1.

Julia, 375 byte

Saya telah meninggalkan lekukan untuk dibaca, tetapi jumlah byte tanpa itu.

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

Yang ini hanyalah port Julia langsung dari solusi Python brilian PM 2Ring. Saya merasa lapar, jadi saya memutuskan bahwa saya menginginkan kue itu. Sangat menarik untuk melihat persamaan dan perbedaan antara kedua bahasa. Saya menerapkan itertools.groupby(dalam bentuk terbatas) sebagai g(w).

Tapi logikanya bukan milikku, jadi pergi dan pilih jawaban PM 2Ring .

Ganti f=factorialdengan f(x)=factorial(BigInt(x))jika Anda ingin dapat menangani input besar seperti p ("QUARTZGLYPHJOBVEXDCWMFINKS").

MATL , 13 12 11 byte

1 byte disimpan berkat GB !

tY@Xu=!Af1)

Output berbasis 1.

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

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 byte

Mengubah spec masalah memungkinkan penghematan 2 byte.

Permutations@Sort@#~Position~#&

Fungsi murni mengambil daftar sebagai input dan mengembalikan bilangan bulat negatif Ndalam formulir {{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)

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

Uji

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 byte

q_e!\a#

Cobalah online!

Pyth, 5 byte

xS{.p

Penerjemah online

Mengambil input yang dikutip.

Scala, 40 byte

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

Untuk menggunakannya, tetapkan fungsi ini ke variabel:

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

Cobalah online di ideone

Sayangnya, permutationsmengembalikan iterator, yang tidak memiliki sortedmetode, jadi harus dikonversi ke aSeq

C ++, 96 byte

Kita dapat memanfaatkan sepenuhnya pustaka standar di sini. Daftar huruf dilewatkan sebagai iterator awal / akhir dalam gaya C ++ standar.

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

Kami tidak perlu membuat semua permutasi - karena kami memiliki transformasi dari satu permutasi ke pendahulunya, kami hanya menghitung berapa banyak iterasi yang diperlukan untuk mencapai nilai nol.

Program uji:

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

Hasil tes:

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

Japt, 6 byte

Diindeks 0

ñ á bU

Cobalah

Ruby, 50 byte

Saya berharap ini lebih pendek. Saya tidak akan menambahkan sortjika dokumen tidak mengatakan "implementasi tidak memberikan jaminan tentang urutan permutasi yang dihasilkan."

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