Definição

A classificação de uma palavra é definida como a posição da palavra quando todas as permutações (ou arranjos) possíveis de suas letras são organizadas em ordem alfabética, como em um dicionário, independentemente de as palavras serem significativas ou não.

Vamos considerar essas duas palavras - "azul" e "visto". Para começar, escreveríamos todos os arranjos possíveis das letras dessas palavras em ordem alfabética:

"blue": "belu","beul","bleu","blue","buel","bule","eblu","ebul","elub","elbu","eubl",
        "eulb","lbeu","lbue","lebu","leub","lube","lueb","ubel","uble","uebl","uelb",
        "ulbe","uleb"
"seen": "eens","eesn","enes","ense","esen","esne","nees","nese","nsee","seen",
        "sene","snee"

Agora vamos olhar da esquerda e encontrar a posição das palavras que precisamos. Vemos que a palavra "azul" está na 4ª posição e "vista" está na 10ª posição. Portanto, a classificação da palavra "azul" é 4, e a de "visto" é 10. Essa é a maneira geral de calcular a classificação de uma palavra. Certifique-se de começar a contar apenas de 1.

Tarefa

Sua tarefa é escrever um código para receber qualquer palavra como entrada e exibir sua classificação. A classificação deve ser a saída. Tenha cuidado com as palavras que contêm letras repetidas.

Exemplos

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

Você pode assumir que a entrada esteja completamente em minúscula e a entrada conterá apenas caracteres alfabéticos . Além disso, se um espaço em branco ou uma sequência inválida for inserida, você poderá retornar qualquer coisa.

Pontuação

Isso é código-golfe , então o código mais curto vence!

Gaia , 4 bytes

fuȯI

Experimente online!

Python 3 , 71 bytes

lambda s:sum(t<=(*s,)for t in{*permutations(s)})
from itertools import*

Experimente online!

05AB1E , 5 bytes

ϐsk>

Experimente online! ou como um conjunto de testes

Explicação

œ       # get permutations of input
 ê      # sort and remove duplicates
  s     # swap input to top of stack
   k    # get index of input in the list
    >   # increment

Pitão , 6 bytes

hxS{.p

Suíte de teste.

Explicação

hxS {.p || Programa completo.

    .p || Todas as permutações da entrada.
   {|| Desduplicar.
  S || Ordenar.
 x || Índice da entrada nesta lista.
h || Incremento.

Geléia , 5 bytes

Œ!ṢQi

Experimente online! ou veja a suíte de testes

Como funciona

Œ!ṢQi - Main link. Argument: s (string)      e.g. 'baa'
Œ!    - All permutations                          ['baa', 'baa', 'aba', 'aab', 'aba', 'aab']
  Ṣ   - Sort                                      ['aab', 'aab', 'aba', 'aba', 'baa', 'baa']
   Q  - Deduplicate                               ['aab', 'aba', 'baa']
    i - 1-based index of s                        3

Python 2 , 78 bytes

lambda s:-~sorted(set(permutations(s))).index(tuple(s))
from itertools import*

Experimente online!

Python 3 , 73 bytes

• Agradecemos ao Sr. Xcoder por escolher o Python 3; economizando cinco bytes.

lambda s:-~sorted({*permutations(s)}).index((*s,))
from itertools import*

Experimente online!

CJam , 8 bytes

q_e!\a#)

Experimente online!

+1 byte devido a um requisito indexado a 1.

Haskell , 56 bytes

import Data.List
elemIndex<*>([]:).nub.sort.permutations

Experimente online!

+6 bytes devido ao requisito de 1 indexação. :(

Japonês , 8 10 bytes

Indexado a 0. Poxy, indexação 1 desnecessária, aumentando minha contagem de bytes em 25%!

á â n bU Ä

Teste-o

Explicação

áobtém todas as permutações da entrada, âremove duplicatas, as nclassifica e bobtém o índice da primeira ocorrência da entrada U,.

J , 28 23 bytes

-5 bytes graças ao FrownyFrog

1+/:~@~.@(A.~i.@!@#)i.]

Como funciona?

                      ] - the argument
         (A.~      )    - permutations in the 
             i.@!@#     - range 0 to factorial of the arg. length
  /:~@~.@               - remove duplicates and sort
                    i.  - index of arg. in the sorted list
1+                      - add 1 (for 1-based indexing)

Experimente online!

Tcl, 196 bytes

proc p {a p} {if {$a eq {}} {lappend ::p $p} {while {[incr n]<=[llength $a]} {p [lreplace $a $n-1 $n-1] $p[lindex $a $n-1]}}}
p [split $argv ""] ""
puts [expr [lsearch [lsort -unique $p] $argv]+1]

O Tcl não possui um método interno para calcular a próxima permutação lexicográfica, por isso temos que fazer isso sozinhos. Mas espere ... é mais curto fazê-lo com uma função recursiva simples que calcula todas as permutações possíveis em qualquer ordem.

Ungolfed:

# Compute all possible permutations of the argument list
# Puts the result in ::all_permutations
proc generate_all_permutations {xs {prefixes ""}} {
  if {$xs eq {}} {
    lappend ::all_permutations $prefixes
  } else {
    while {[incr n] <= [llength $xs]} {
      generate_all_permutations [lreplace $xs $n-1 $n-1] $prefixes[lindex $xs $n-1]
    } 
  }
}

# Get our input as command-line argument, turn it into a list of letters
generate_all_permutations [split $argv ""]

# Sort, remove duplicates, find the original argument, and print its 1-based index
puts [expr [lsearch [lsort -unique $all_permutations] $argv]+1]

K (oK) , 23 18 bytes

Solução:

1+*&x~/:?x@prm@<x:

Experimente online!

Exemplos:

1+*&x~/:?x@prm@<x:"seen"
10
1+*&x~/:?x@prm@<x:"blue"
4

Explicação:

Gere permutações dos índices da string de entrada classificada, use-os para indexar de volta para a string de entrada, faça distinções, veja onde a string original correspondeu e adicione um.

1+*&x~/:?x@prm@<x: / the solution
                x: / save input string as x
               <   / return indices when sorting x ascending
           prm@    / apply (@) function prm
         x@        / index into x with these permutations
        ?          / distinct (remove duplicates)
    x~/:           / apply match (~) between x and each-right (/:)
   &               / return indexes where true (ie the match)
  *                / take the first one
1+                 / add 1 due to 1-indexing requirement

Java 8, 211 bytes

import java.util.*;TreeSet q=new TreeSet();s->{p("",s);return-~q.headSet(s).size();}void p(String p,String s){int l=s.length(),i=0;if(l<1)q.add(p);for(;i<l;p(p+s.charAt(i),s.substring(0,i)+s.substring(++i,l)));}

Explicação:

Experimente online.

import java.util.*;        // Required import for TreeSet

TreeSet q=new TreeSet();   // Sorted Set on class-level

s->{                       // Method with String parameter and integer return-type
  p("",s);                 //  Save all unique permutations of the String in the sorted set
  return-~q.headSet(s).size();}
                           //  Return the 0-indexed index of the input in the set + 1

void p(String p,String s){ // Separated method with 2 String parameters and no return-type
  int l=s.length(),        //  The length of the String `s`
      i=0;                 //  Index integer, starting at 0
  if(l<1)                  //  If String `s` is empty
    q.add(p);              //   Add `p` to the set
  for(;i<l;                //  Loop from 0 to `l` (exclusive)
    p(                     //   Do a recursive call with:
      p+s.charAt(i),       //    `p` + the character at the current index of `s` as new `p`
      s.substring(0,i)+s.substring(++i,l)));}
                           //    And `s` minus this character as new `s`

Python 3 , 183 182 bytes

A primeira resposta que é executada em tempo polinomial!

a=[*map(ord,input())]
f=lambda x:x and x*f(x-1)or 1
c=[0]*98
for C in a:c[C]+=1
l=len(a)
F=f(l)
for i in c:F//=f(i)
r=1
for x in a:F//=l;l-=1;r+=sum(c[:x])*F;F*=c[x];c[x]-=1
print(r)

Experimente online!

Exija que a entrada seja toda em maiúscula, porque ... ela salva um byte.

Programa completo, leva entrada stdine saída para stdout.

Nomes de variáveis: (tipo de código não armazenado)

a : permu
f : factorial
c : count_num
C : char
l : n_num_left
F : factor
r : result

Infelizmente, from math import factorial as fleva exatamente mais 1 byte.

(Nota não relacionada: verifiquei o Combinatorica`pacote do Mathematica, nada de útil, inclusive RankPermutation)

Casca , 6 bytes

S€(OuP

Experimente online! Eu sinto que deveria haver uma maneira de desistir (.

Explicação:

 €     -- return index of the input 
S (    -- in the list generated by applying the following functions to the input:
     P -- permutations
    u  -- remove duplicates
   O   -- sort

Limpo , 113 111 bytes

import StdEnv,StdLib
?s=elemIndex s[[]:removeDup(foldr(\a b=sort[insertAt i a x\\x<-b,i<-[0..length x]])[[]]s)]

Experimente online!

+3 bytes para lidar com a indexação 1: /

APL (Dyalog Unicode) , 33 bytes (SBCS)

⎕CY'dfns'
{∪⊃∘(⍵[⍋⍵])¨¨↓pmat≢⍵}⍳⊂

Experimente online!

Python 3 , 105 104 103 bytes

f=lambda s:s==s*2or f(s[1:])+sum(f(sorted(s[:s.index(c)]+s[s.index(c)+1:])[::-1])for c in{*s}if c<s[0])

Experimente online!

Ruby , 49 bytes

->w{c=w.chars
1+c.sort.permutation.uniq.index(c)}

Experimente online!

JavaScript (ES6), 106 100 bytes

w=>(P=(a,s)=>a[0]?a.map((_,i)=>P(b=[...a],s+b.splice(i,1))):P[s]=P[s]||++k)[P([...w].sort(),k=''),w]

Casos de teste

let f =

w=>(P=(a,s)=>a[0]?a.map((_,i)=>P(b=[...a],s+b.splice(i,1))):P[s]=P[s]||++k)[P([...w].sort(),k=''),w]

console.log(f("prime"))  // 94
console.log(f("super"))  // 93
console.log(f("bless"))  // 4
console.log(f("speech")) // 354
console.log(f("earth"))  // 28
console.log(f("a"))      // 1
console.log(f("abcd"))   // 1
console.log(f("baa"))    // 3

Quão?

P () é a nossa função de permutação recursiva. Mas o objeto abrangente de P também é usado para armazenar as fileiras das permutações.

P = (a, s) =>               // given an array of letters a[] and a string s
  a[0] ?                    // if a[] is not empty:
    a.map((_, i) =>         //   for each entry at position i in a[]:
      P(                    //     do a recursive call to P() with:
        b = [...a],         //       a copy b[] of a[], with a[i] removed
        s + b.splice(i, 1)  //       the extracted letter appended to s
      )                     //     end of recursive call
    )                       //   end of map()
  :                         // else:
    P[s] = P[s] || ++k      //   if P[s] is not already defined, set it to ++k

O código de embalagem agora é lido como:

w =>                        // given the input word w
  P[                        // return the permutation rank for w
    P(                      //   initial call to P() with:
      [...w].sort(),        //     the lexicographically sorted letters of w
      k = ''                //     s = k = '' (k is then coerced to a number)
    ),                      //   end of call
    w                       //   actual index used to read P[]
  ]                         // end of access to P[]

C ++, 230 bytes

#include<algorithm>
#include<iostream>
#include<string>
using namespace std;void R(string s){int n=1;auto p=s;sort(begin(p),end(p));do if(p==s)cout<<n;while(++n,next_permutation(begin(p),end(p)));}int main(int n,char**a){R(a[1]);}

Conforme minha pergunta, o código definitivamente precisa ser executável como está. A cláusula somente de função é basicamente lixo. : - @

Agradeço a quem gentilmente respondeu à pergunta sobre o que pode ser cortado para mim. No interesse do código válido , evitei o popular GCC-ism de incluir <bits / stdc ++. H>, que sempre considerei uma fraude de brecha.

O que se segue é o que resta da minha postagem original:

Aqui, ele é destruído com os cabeçalhos necessários, etc:

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

void R( string s )
{
  int n = 1;
  auto p = s;
  sort( begin(p), end(p) );
  do if (p == s) cout << n;
  while (++n, next_permutation( begin(p), end(p) ));
}

int main( int n, char** a )
{
  R( a[1] );
}

Isso atinge até 230 bytes, um terço do padrão exigido por todos os programas C ++. (Portanto, não me sinto muito mal por não contar, mas como nunca vi uma queixa firme de qualquer maneira, o OP terá que me dizer o que ele prefere satisfazer “escreva um código para usar qualquer palavra como entrada e exibir sua classificação. ”)

Também não tenho certeza se isso satisfaz "a classificação deve ser gerada".

Perl 5 , 98 + 3 ( -pF) = 101 bytes

$"=',';@a=grep{++$k{$_}<=1&&"@F"eq join$",sort/./g}sort glob"{@F}"x(@F=sort@F);1while!/$a[$\++]/}{

Experimente online!

Oitava , 43 bytes

@(s)find(all(unique(perms(s),'rows')==s,2))

Experimente online!

Perl 6 , 53 bytes

{1+first :k,$_,.comb.permutations».join.unique.sort}

Experimente online!

PowerShell , 275 bytes

param($s)function n($a){if($a-eq1){return}0..($a-1)|%{n($a-1);if($a-eq2){$b.ToString()}$p=($j-$a);[char]$t=$b[$p];for($z=($p+1);$z-lt$j;$z++){$b[($z-1)]=$b[$z]}$b[($z-1)]=$t}}if($s.length-eq1){1;exit}$b=New-Object Text.StringBuilder $s;(n($j=$s.length)|sort -u).indexOf($s)+1

Experimente online!

Então, isso é uma bagunça sangrenta.

O PowerShell não possui permutações internas; portanto, esse código usa o algoritmo daqui (com muita intensidade), disponível sob a Licença Pública Limitada da Microsoft ( Anexo B nesta página de licenciamento).

O programa recebe a entrada $scomo uma string e o programa atual começa com $b=New-Object .... Estamos construindo um novo objeto StringBuilder , que é (essencialmente) uma sequência de caracteres mutável. Isso nos permitirá lidar com as permutações mais facilmente. Em seguida, chamamos a função n(definindo $jao longo do caminho o comprimento da string de entrada), sortcom o -usinalizador nique de saída, pegamos o .indexOf()para encontrar a string de entrada e adicionamos 1porque o PowerShell é zero-indexado.

A função é a parte principal do programa. Ele assume como entrada um número e cada iteração é decrescente até alcançarmos 1(ou seja, uma única letra). O restante da função essencialmente chama recursivamente a função, pega a letra atual e a itera em todas as posições.

Há um único bit adicional de lógica if($s.length-eq1){1;exit}para considerar as seqüências de caracteres de comprimento 1devido a como a função de permutações funciona.

Pyt , 5 bytes

ĐᒆỤ≥Ʃ

Explicação:

            Implicit input
Đ           Duplicate input
 ᒆ         Get list of all permutations of input
  Ụ         Get unique permutations
   ≥        Does each permutation come before or is equal to the input?
    Ʃ       Sum of result of previous step (converts booleans to ints)

Experimente online!