Входные данные: последовательность заглавных букв (ASCII [65; 90]), которая является N- й * лексикографической перестановкой мультимножества его символов

* перестановки пронумерованы от 0 или 1 и выше

Вывод: основание-10, целое число N

Rulez

• Там могут быть дубликаты (вот как этот вызов отличается от этого )
• Символы упорядочены по значению ASCII
• В случае ввода длины, меньшей или равной 1, вводом является первая перестановка, а результатом является 0или 1соответственно
• Первая перестановка - это та, в которой крайний левый символ имеет самое низкое значение, самый правый символ имеет наибольшее значение, а последовательность символов между первым и последним символом является первой перестановкой мультимножества его символов (рекурсивное определение!)
• Кратчайшие выигрыши

пример

• Ввод AABпроизводит вывод0
• Ввод ABAпроизводит вывод1
• Ввод BAAпроизводит вывод2

• Ввод ZZZпроизводит вывод0
• Ввод DCBAпроизводит вывод23

РЕДАКТИРОВАТЬ

Дополнительная благодарность тому, кто может придумать решение, которое не производит все перестановки, а затем искать вход. Это какая-то проблема.

Желе , 5 байт

Œ!QṢi

Попробуйте онлайн!

1-индексированный выход.

Python 2, 69 байт

Попробуйте онлайн

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

Python, 302 287 байт

Мертвый Опоссум уже опубликовал краткое Pythonic решение, поэтому я решил пойти на дополнительные похвалы. Это решение не генерирует все перестановки. Он может быстро вычислить индекс перестановки довольно большой строки; он также правильно обрабатывает пустую строку.

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

Тестовый код:

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)

выход

 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

Версия без гольфа:

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

Около lexico_permute_string

Этот алгоритм, из-за Нараяна Пандита, из https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Произвести следующую перестановку в лексикографическом порядке последовательности a

1. Найдите наибольший индекс j такой, что a [j] <a [j + 1]. Если такого индекса не существует, перестановка является последней перестановкой.
2. Найдите наибольший индекс k, больший чем j, такой, что a [j] <a [k].
3. Поменяйте местами значение a [j] со значением a [k].
4. Переверните последовательность от a [j + 1] до последнего элемента a [n] и включите его.

FWIW, вы можете увидеть аннотированную версию этой функции здесь .

FWIW, вот обратная функция.

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

выход

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

А вот функция, которую я написал при разработке, perm_unrankкоторая показывает разбивку субсчетов.

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)

выход

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 байтов

œêJ¹k

Использует кодировку CP-1252 . Попробуйте онлайн!

05AB1E , 5 байтов

œê¹Sk

Попробуйте онлайн!

Независимо от ответа Аднана.

PHP, 124 байта

$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 байт

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

Онлайн версия

Бежать с

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

Рассчитать с факториалом

Расширенная версия

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

Вывод для строки 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
)

Онлайн версия

Юлия, 121 125 байт

Неконкурентоспособен, так как неправильно обрабатывает дубликаты букв. Я перенес это из другого языка, из части решения проблемы Project Euler, которую я сделал несколько лет назад, и первая 121-байтовая версия имела ошибку, потому что я транспонировал использование переставленной строки и отсортированной канонической ссылки. строка.

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)

Для больших входов эта версия использует bignums стоимостью 8 дополнительных байтов:

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

Использует факторную систему счисления , qv. Таким образом, она не производит все перестановки и для больших входов будет работать намного быстрее, чем те, которые делают.

Например, алфавит можно перевести в довольно надуманное предложение «Кварцевый глиф задание vex'd cwm finks». Это предложение представляет собой 259 985 607 122 (42 410 643 097 474 123) лексикографической перестановки букв алфавита. (Приблизительно 260 перестановок септиллионов.) Эта программа обнаруживает, что примерно за 65 мкс на моей машине.

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

Обратите внимание, что число заканчивается на ... 122, а не ... 123, потому что OP запросил, чтобы перестановки были пронумерованы от 0, а не от 1.

Юлия, 375 байт

Я оставил отступ для удобства чтения, но счетчик байтов без него.

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

Это просто порт Джулии от великолепного решения Python от PM 2Ring. Я проголодался и решил, что мне все-таки нужно печенье. Интересно увидеть сходства и различия между двумя языками. Я реализовалitertools.groupby (в ограниченной форме) как g(w).

Но логика не моя, так что иди и проголосуй за PM 2Ring ответ .

Замените f=factorialна, f(x)=factorial(BigInt(x))если вы хотите иметь возможность обрабатывать большие вводы, такие как p ("QUARTZGLYPHJOBVEXDCWMFINKS").

МАТЛ , 13 12 11 байт

1 байт сохранен благодаря ГБ !

tY@Xu=!Af1)

Выход основан на 1.

Попробуйте онлайн! Или проверьте все тестовые случаи .

объяснение

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 байт

Изменение спецификации проблемы позволило сэкономить 2 байта.

Permutations@Sort@#~Position~#&

Чистая функция, принимающая список в качестве входных данных и возвращающая неотрицательное целое число Nв форме {{N}}.

JavaScript (ES6), 130 байт

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)

Меньше гольфа

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
}

Тестовое задание

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 байтов

q_e!\a#

Попробуйте онлайн!

Pyth, 5 байт

xS{.p

Онлайн переводчик

Принимает цитируемые данные.

Скала, 40 байт

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

Чтобы использовать его, назначьте эту функцию переменной:

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

Попробуйте онлайн в Ideone

К сожалению, permutationsвозвращает итератор, у которого нет sortedметода, поэтому он должен быть преобразован вSeq

C ++, 96 байт

Мы можем в полной мере использовать стандартную библиотеку здесь. Список писем передается как начальный / конечный итераторы в стандартном стиле C ++.

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

Нам не нужно генерировать все перестановки - поскольку у нас есть преобразование из одной перестановки в ее предшественницу, мы просто считаем, сколько итераций требуется для достижения нулевого значения.

Тестовая программа:

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

Результаты теста:

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

Japt, 6 байт

0 индексированные

ñ á bU

Попытайся

Рубин, 50 байтов

Я ожидал, что это будет короче. Я бы не добавил, sortесли бы в документах не говорилось, что «реализация не дает никаких гарантий относительно порядка, в котором получаются перестановки».

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