Definición

El rango de una palabra se define como la posición de la palabra cuando todas las permutaciones (o arreglos) posibles de sus letras se ordenan alfabéticamente, como en un diccionario, sin importar si las palabras son significativas o no.

Consideremos estas dos palabras: "azul" y "visto". Para comenzar, escribiríamos todos los arreglos posibles de las letras de estas palabras en orden alfabético:

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

Ahora miremos desde la izquierda y encontremos la posición de las palabras que necesitamos. Vemos que la palabra "azul" está en la cuarta posición y "visto" está en la décima posición. Entonces, el rango de la palabra "azul" es 4, y el de "visto" es 10. Esta es la forma general de calcular el rango de una palabra. Asegúrese de comenzar a contar solo desde 1.

Tarea

Su tarea es escribir un código para tomar cualquier palabra como entrada y mostrar su rango. El rango debe ser la salida. Tenga cuidado con las palabras que contienen letras repetidas.

Ejemplos

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

Puede suponer que la entrada está completamente en minúsculas y la entrada solo contendrá caracteres alfabéticos . Además, si se ingresa un espacio en blanco o una cadena no válida, puede devolver cualquier cosa.

Tanteo

Este es el código de golf , por lo que gana el código más corto.

Gaia , 4 bytes

fuȯI

Pruébalo en línea!

Python 3 , 71 bytes

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

Pruébalo en línea!

05AB1E , 5 bytes

ϐsk>

Pruébalo en línea! o como un conjunto de pruebas

Explicación

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

Pyth , 6 bytes

hxS{.p

Banco de pruebas.

Explicación

hxS {.p || Programa completo

    .p || Todas las permutaciones de la entrada.
   {|| Deduplicar
  S || Ordenar.
 x || Índice de la entrada en esta lista.
h || Incremento.

Jalea , 5 bytes

Œ!ṢQi

Pruébalo en línea! o ver el conjunto de pruebas

Cómo 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*

Pruébalo en línea!

Python 3 , 73 bytes

• Gracias al Sr. Xcoder por elegir Python 3; ahorrando cinco bytes.

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

Pruébalo en línea!

CJam , 8 bytes

q_e!\a#)

Pruébalo en línea!

+1 byte debido a un requisito indexado 1.

Haskell , 56 bytes

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

Pruébalo en línea!

+6 bytes debido al requisito de 1 indexación. :(

Japt , 8 10 bytes

0 indexado. ¡Poxy, indexación 1 innecesaria, aumentando mi recuento de bytes en un 25%!

á â n bU Ä

Pruébalo

Explicación

á obtiene todas las permutaciones de la entrada, â Elimina los duplicados, nlos ordena y bobtiene el índice de la primera aparición de la entrada, U.

J , 28 23 bytes

-5 bytes gracias a FrownyFrog

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

¿Cómo 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)

Pruébalo en línea!

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]

Tcl no tiene un método incorporado para calcular la próxima permutación lexicográfica, por lo que debemos hacerlo nosotros mismos. Pero espera ... es más corto hacerlo con una función recursiva simple que calcula todas las permutaciones posibles en cualquier orden.

Sin golf:

# 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

Solución:

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

Pruébalo en línea!

Ejemplos:

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

Explicación:

Genere permutaciones de los índices de la cadena de entrada ordenada, úselas para indexar nuevamente en la cadena de entrada, tome las distinciones, vea dónde coincide la cadena original y agregue una.

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

Explicación:

Pruébalo en línea.

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

La primera respuesta que se ejecuta en tiempo 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)

Pruébalo en línea!

Requiere que la entrada sea todo en mayúsculas, porque ... guarda un byte.

Programa completo, toma entrada stdiny salida a stdout.

Nombres de variables: (tipo de código no protegido)

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

Desafortunadamente, from math import factorial as ftoma exactamente 1 byte más.

(Nota no relacionada: revisé el Combinatorica`paquete de Mathematica, nada útil, incluido RankPermutation)

Casco , 6 bytes

S€(OuP

Pruébalo en línea! Siento que debería haber una manera de caer (.

Explicación:

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

Limpio , 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)]

Pruébalo en línea!

+3 bytes para manejar la indexación 1: /

APL (Dyalog Unicode) , 33 bytes (SBCS)

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

Pruébalo en línea!

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

Pruébalo en línea!

Ruby , 49 bytes

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

Pruébalo en línea!

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 prueba

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

¿Cómo?

P () es nuestra función de permutación recursiva. Pero el objeto que abarca P también se usa para almacenar los rangos de las permutaciones.

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

El código de ajuste ahora se lee 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]);}

Según mi pedido, el código definitivamente debe ser ejecutable tal como está. La cláusula de solo función es básicamente basura. : - @

Gracias a quienes amablemente respondieron la pregunta de qué se puede cortar para mí. En interés de válido código , he evitado el popular GCC-ism de incluir <bits / stdc ++. H>, que siempre he considerado una trampa falsa.

Lo que sigue es lo que queda de mi publicación original:

Aquí no tiene los encabezados necesarios, 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] );
}

Que los campos de golf se reducen a 230 bytes, un tercio de ese estándar requerido por cada programa C ++. (Por lo tanto, no me siento tan mal sin contarlo, pero como nunca he visto una queja firme de ninguna manera, OP tendrá que decirme qué prefiere satisfacer "escriba un código para tomar cualquier palabra como entrada" y mostrar su rango ".)

Tampoco estoy seguro de si esto satisface "el rango debería ser el resultado".

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[$\++]/}{

Pruébalo en línea!

Octava , 43 bytes

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

Pruébalo en línea!

Perl 6 , 53 bytes

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

Pruébalo en línea!

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

Pruébalo en línea!

Entonces, esto es un desastre sangriento.

PowerShell no tiene ninguna permutaciones incorporada, por lo que este código utiliza el algoritmo de aquí (mucho golf), que está disponible bajo la Licencia pública limitada de Microsoft ( Anexo B en esta página de licencias).

El programa toma la entrada $scomo una cadena, luego el programa real comienza con $b=New-Object .... Estamos construyendo un nuevo objeto StringBuilder , que es (esencialmente) una cadena mutable de caracteres. Esto nos permitirá manejar las permutaciones más fácilmente. Luego llamamos a la función n(configurada $jen el camino para que sea la longitud de la cadena de entrada), sortcon la -umarca nique como salida, tome.indexOf() para encontrar la cadena de entrada y agreguemos 1porque PowerShell está indexado a cero.

La función es la parte principal del programa. Toma como entrada un número, y cada iteración contará hasta que alcancemos1 (es decir, una sola letra). El resto de la función esencialmente llama recursivamente a la función, así como toma la letra actual y la itera en cada posición.

Hay un solo bit de lógica adicional if($s.length-eq1){1;exit}para tener en cuenta las cadenas de entrada de longitud 1debido a cómo funciona la función de permutaciones.

Pyt , 5 bytes

ĐᒆỤ≥Ʃ

Explicación:

            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)

Pruébalo en línea!