Definicja

Ranga słowa jest definiowana jako pozycja słowa, gdy wszystkie możliwe kombinacje (lub układy) jego liter są ułożone alfabetycznie, jak w słowniku, bez względu na to, czy słowa są znaczące, czy nie.

Rozważmy te dwa słowa - „niebieski” i „widziany”. Na początek piszemy wszystkie możliwe układy liter tych słów w kolejności alfabetycznej:

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

Teraz spójrzmy od lewej strony i znajdź pozycję potrzebnych nam słów. Widzimy, że słowo „niebieski” znajduje się na 4 pozycji, a „widziany” na 10 pozycji. Zatem ranga słowa „niebieski” wynosi 4, a ranga „widziany” to 10. Jest to ogólny sposób obliczania rangi słowa. Upewnij się, że zaczynasz liczyć tylko od 1.

Zadanie

Twoim zadaniem jest napisanie kodu, który przyjmie dowolne słowo jako dane wejściowe i wyświetli jego pozycję. Ranga powinna być wynikiem. Uważaj na słowa zawierające powtarzające się litery.

Przykłady

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

Możesz założyć, że dane wejściowe są całkowicie pisane małymi literami, a dane wejściowe będą zawierać tylko znaki alfabetyczne . Również jeśli zostanie wprowadzona spacja lub niepoprawny ciąg, możesz zwrócić cokolwiek.

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy kod!

Gaia , 4 bajty

fuȯI

Wypróbuj online!

Python 3 , 71 bajtów

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

Wypróbuj online!

05AB1E , 5 bajtów

ϐsk>

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

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

hxS{.p

Zestaw testowy.

Wyjaśnienie

hxS {.p || Pełny program

    .p || Wszystkie permutacje danych wejściowych.
   {|| Deduplikacja.
  S || Sortować.
 x || Indeks danych wejściowych na tej liście.
h || Przyrost.

Galaretka , 5 bajtów

Œ!ṢQi

Wypróbuj online! lub zobacz zestaw testowy

Jak to działa

Œ!Ṣ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 bajtów

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

Wypróbuj online!

Python 3 , 73 bajty

• Dziękujemy Panu Xcoderowi za wybór Pythona 3; oszczędzając pięć bajtów.

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

Wypróbuj online!

CJam , 8 bajtów

q_e!\a#)

Wypróbuj online!

+1 bajt ze względu na wymaganie 1-indeksowane.

Haskell , 56 bajtów

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

Wypróbuj online!

+6 bajtów z powodu wymogu 1-indeksowania. :(

Japt , 8 10 bajtów

0-indeksowane. Poxy, niepotrzebne indeksowanie 1, zwiększając moją liczbę bajtów o 25%!

á â n bU Ä

Sprawdź to

Wyjaśnienie

ápobiera wszystkie permutacje wejściu, âusuwa duplikaty, nsortuje je i bdostaje indeks pierwszego wystąpienia wejściu, U.

J , 28 23 bajtów

-5 bajtów dzięki FrownyFrog

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

Jak to działa?

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

Wypróbuj online!

Tcl, 196 bajtów

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 nie ma wbudowanej metody obliczania następnej permutacji leksykograficznej, więc musimy to zrobić sami. Ale poczekaj ... jest to krótsze, aby to zrobić za pomocą prostej funkcji rekurencyjnej, która oblicza wszystkie możliwe permutacje w dowolnej kolejności.

Nie golfowany:

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

Rozwiązanie:

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

Wypróbuj online!

Przykłady:

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

Wyjaśnienie:

Wygeneruj permutacje indeksów posortowanego ciągu wejściowego, użyj ich, aby zindeksować z powrotem ciąg wejściowy, weź różnice, zobacz, gdzie pasował oryginalny ciąg, i dodaj jeden.

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

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

Wyjaśnienie:

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

Pierwsza odpowiedź, która działa w czasie wielomianowym!

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)

Wypróbuj online!

Wymagaj, aby dane wejściowe były pisane wielkimi literami, ponieważ ... zapisuje bajt.

Pełny program pobiera dane wejściowe stdini wyjściowe stdout.

Nazwy zmiennych: (rodzaj nieoznakowanego kodu)

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

Niestety from math import factorial as fzajmuje dokładnie 1 bajt więcej.

(Niepowiązana uwaga: sprawdziłem Combinatorica`pakiet Mathematica, nic przydatnego, w tym RankPermutation)

Łuska , 6 bajtów

S€(OuP

Wypróbuj online! Czuję, że powinien istnieć sposób na upuszczenie (.

Wyjaśnienie:

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

Czysty , 113 111 bajtów

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

Wypróbuj online!

+3 bajty do obsługi indeksowania 1: /

APL (Dyalog Unicode) , 33 bajty (SBCS)

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

Wypróbuj online!

Python 3 , 105 104 103 bajty

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

Wypróbuj online!

Rubinowy , 49 bajtów

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

Wypróbuj online!

JavaScript (ES6), 106 100 bajtów

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]

Przypadki testowe

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

W jaki sposób?

P () to nasza rekurencyjna funkcja permutacji. Ale otaczający obiekt P służy również do przechowywania szeregów permutacji.

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

Kod owijania brzmi teraz:

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

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

Zgodnie z moim pytaniem kod zdecydowanie musi być wykonywalny w obecnej postaci. Klauzula tylko funkcji jest w zasadzie śmieciami. : - @

Dziękuję tym, którzy uprzejmie odpowiedzieli na pytanie, co można dla mnie wyciąć. W interesie poprawnego kodu uniknąłem popularnego GCC obejmującego <bits / stdc ++. H>, co zawsze uważałem za kiepskie oszustwo.

Oto, co pozostało z mojego oryginalnego posta:

Tutaj jest on niepolecany z niezbędnymi nagłówkami itp .:

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

To gra w golfa do 230 bajtów, jednej trzeciej standardowej płyty wymaganej przez każdy program C ++. (Więc nie czuję się tak źle, nie licząc tego, ale ponieważ nigdy nie widziałem stanowczej skargi w żaden sposób, OP będzie musiał mi powiedzieć, który woli spełnić „napisz kod, aby wziąć dowolne słowo jako dane wejściowe i wyświetlać swoją pozycję. ”)

Nie jestem również pewien, czy to spełnia „pozycję należy wyliczyć”.

Perl 5 , 98 + 3 ( -pF) = 101 bajtów

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

Wypróbuj online!

Oktawa , 43 bajty

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

Wypróbuj online!

Perl 6 , 53 bajtów

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

Wypróbuj online!

PowerShell , 275 bajtów

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

Wypróbuj online!

To jest cholerny bałagan.

PowerShell nie ma wbudowanych permutacji, więc ten kod korzysta z algorytmu z tego miejsca (intensywnie grał w golfa), który jest dostępny na licencji Microsoft Limited Public License ( załącznik B na tej stronie licencjonowania).

Program pobiera dane wejściowe $sjako ciąg znaków, a następnie rozpoczyna się rzeczywisty program $b=New-Object .... Budujemy nowy obiekt StringBuilder , który jest (zasadniczo) zmiennym ciągiem znaków. Pozwoli nam to łatwiej obsługiwać permutacje. Następnie wywołujemy funkcjęn (ustawiając $jprzy tym długość łańcucha wejściowego), sortz -uflagą nique na wyjściu, bierzemy, .indexOf()aby znaleźć łańcuch wejściowy i dodajemy, 1ponieważ PowerShell jest indeksowany na zero.

Ta funkcja jest główną częścią programu. Pobiera na wejściu liczbę i każda iteracja odlicza do osiągnięcia 1(tj. Pojedynczej litery). Reszta funkcji zasadniczo rekurencyjnie wywołuje funkcję, a także pobiera bieżącą literę i iteruje ją przez każdą pozycję.

Istnieje jeden dodatkowy element logiki if($s.length-eq1){1;exit}do uwzględnienia łańcuchów wejściowych długości 1ze względu na działanie funkcji permutacji.

Pyt , 5 bajtów

ĐᒆỤ≥Ʃ

Wyjaśnienie:

            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)

Wypróbuj online!