Definition

Der Rang eines Wortes ist definiert als die Position des Wortes, wenn alle möglichen Permutationen (oder Anordnungen) seiner Buchstaben alphabetisch angeordnet sind, wie in einem Wörterbuch, unabhängig davon, ob die Wörter bedeutungsvoll sind oder nicht.

Betrachten wir diese beiden Wörter - "blau" und "gesehen". Zunächst würden wir alle möglichen Anordnungen der Buchstaben dieser Wörter in alphabetischer Reihenfolge schreiben:

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

Nun schauen wir von links und finden die Position der Wörter, die wir brauchen. Wir sehen, dass sich das Wort "blau" an der 4. Position und "gesehen" an der 10. Position befindet. Der Rang des Wortes "blau" ist also 4 und der des Wortes "gesehen" ist 10. Dies ist die allgemeine Methode zur Berechnung des Rangs eines Wortes. Stellen Sie sicher, dass Sie nur mit 1 anfangen zu zählen.

Aufgabe

Ihre Aufgabe ist es, einen Code zu schreiben, der ein beliebiges Wort als Eingabe aufnimmt und dessen Rang anzeigt. Der Rang sollte die Ausgabe sein. Seien Sie vorsichtig mit Wörtern, die wiederholte Buchstaben enthalten.

Beispiele

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

Sie können davon ausgehen, dass die Eingabe vollständig in Kleinbuchstaben erfolgt und nur alphabetische Zeichen enthält . Auch wenn ein Leerzeichen oder eine ungültige Zeichenfolge eingegeben wird, können Sie alles zurückgeben.

Wertung

Das ist Code-Golf , also gewinnt der kürzeste Code!

Gaia , 4 Bytes

fuȯI

Probieren Sie es online!

Python 3 , 71 Bytes

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

Probieren Sie es online!

05AB1E , 5 Bytes

ϐsk>

Probieren Sie es online! oder als Testsuite

Erläuterung

œ       # 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

Testsuite.

Erläuterung

hxS {.p || Volles Programm.

    .p || Alle Permutationen der Eingabe.
   {|| Deduplizieren
  S || Sortieren.
 x || Index der Eingaben in diese Liste.
h || Zuwachs.

Gelee , 5 Bytes

Œ!ṢQi

Probieren Sie es online! oder sehen Sie sich die Testsuite an

Wie es funktioniert

Œ!Ṣ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*

Probieren Sie es online!

Python 3 , 73 Bytes

• Vielen Dank an Mr. Xcoder, der sich für Python 3 entschieden hat. Einsparung von fünf Bytes.

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

Probieren Sie es online!

CJam , 8 Bytes

q_e!\a#)

Probieren Sie es online!

+1 Byte aufgrund einer 1-indizierten Anforderung.

Haskell , 56 Bytes

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

Probieren Sie es online!

+6 Byte wegen 1-Indexing-Anforderung. :(

Japt , 8 10 Bytes

0-indiziert. Poxy, unnötige 1-Indizierung, erhöht meine Byteanzahl um 25%!

á â n bU Ä

Probier es aus

Erläuterung

áRuft alle Permutationen der Eingabe ab, âentfernt Duplikate, nsortiert sie und bruft den Index des ersten Auftretens der Eingabe ab U.

J , 28 23 Bytes

-5 Bytes dank FrownyFrog

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

Wie es funktioniert?

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

Probieren Sie es 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]

Tcl hat keine eingebaute Methode zur Berechnung der nächsten lexikografischen Permutation, daher müssen wir dies selbst tun. Aber warte ... es ist kürzer , dies mit einer einfachen rekursiven Funktion zu tun, die alle möglichen Permutationen in beliebiger Reihenfolge berechnet .

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

Lösung:

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

Probieren Sie es online!

Beispiele:

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

Erläuterung:

Generieren Sie Permutationen der Indizes der sortierten Eingabezeichenfolge, indizieren Sie sie wieder in die Eingabezeichenfolge, nehmen Sie die Unterscheidungsmerkmale, überprüfen Sie, wo die ursprüngliche Zeichenfolge übereinstimmt, und fügen Sie eine hinzu.

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

Erläuterung:

Probieren Sie es online aus.

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

Die erste Antwort, die im Polynom läuft!

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)

Probieren Sie es online!

Die Eingabe muss in Großbuchstaben erfolgen, da ... ein Byte gespeichert wird.

Vollständiges Programm, nimmt Eingaben von stdinund Ausgaben an stdout.

Variablennamen: (Art ungolfed Code)

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

Dauert leider from math import factorial as fgenau 1 Byte mehr.

(Hinweis ohne Bezug: Ich habe das Combinatorica`Paket von Mathematica überprüft , nichts Nützliches, einschließlich RankPermutation)

Schale , 6 Bytes

S€(OuP

Probieren Sie es online! Ich habe das Gefühl, dass es einen Weg zum Ablegen geben sollte (.

Erläuterung:

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

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

Probieren Sie es online!

+3 Bytes für 1-Indizierung: /

APL (Dyalog Unicode) , 33 Byte (SBCS)

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

Probieren Sie es 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])

Probieren Sie es online!

Ruby , 49 Bytes

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

Probieren Sie es online!

JavaScript (ES6), 106 100 Byte

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]

Testfälle

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

Wie?

P () ist unsere rekursive Permutationsfunktion. Das umgebende Objekt von P wird aber auch zum Speichern der Ränge der Permutationen verwendet.

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

Der Umhüllungscode lautet nun:

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

Gemäß meiner Anfrage muss der Code definitiv so wie er ist ausführbar sein. Die reine Funktionsklausel ist im Grunde genommen Müll. : - @

Vielen Dank an alle, die freundlicherweise die Frage beantwortet haben, was für mich herausgeschnitten werden kann. Im Interesse der Gültigkeit Codes habe ich den beliebten GCC-Ansatz des Einbindens von <bits / stdc ++. H> vermieden, den ich immer als schlechten Schlupfloch-Cheat angesehen habe.

Was folgt ist, was von meinem ursprünglichen Beitrag übrig bleibt:

Hier ist es nicht mit den notwendigen Überschriften usw. bespielt :

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

Das sind bis zu 230 Bytes, ein Drittel der Standardgröße, die jedes C ++ - Programm benötigt. (Also, ich fühle mich nicht schlecht, wenn ich es nicht mitzähle, aber da ich noch nie eine feste Beschwerde gesehen habe, muss OP mir sagen, welche er am liebsten befriedigt. Schreiben Sie einen Code, um ein Wort als Eingabe zu nehmen und zeige seinen Rang an. “)

Ich bin mir auch nicht sicher, ob dies "der Rang sollte ausgegeben werden" erfüllt.

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

Probieren Sie es online!

Oktave , 43 Bytes

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

Probieren Sie es online!

Perl 6 , 53 Bytes

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

Probieren Sie es online!

PowerShell , 275 Byte

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

Probieren Sie es online!

Das ist also eine blutige Sauerei.

In PowerShell sind keine Permutationen integriert. Daher verwendet dieser Code den Algorithmus von hier (mit starkem Golfsport), der unter der Microsoft Limited Public License ( Anhang B auf dieser Lizenzseite) verfügbar ist .

Das Programm nimmt Eingaben $sals String an, dann beginnt das eigentliche Programm mit $b=New-Object .... Wir bauen ein neues StringBuilder- Objekt, bei dem es sich (im Wesentlichen) um eine veränderbare Zeichenfolge handelt. Dadurch können wir die Permutationen einfacher handhaben. Anschließend rufen wir die Funktion auf n(wobei $jdie Länge der Eingabezeichenfolge festgelegt wird), markieren die Ausgabe sortmit -unique .indexOf(), suchen die Eingabezeichenfolge und fügen sie hinzu, 1da PowerShell mit Nullindex versehen ist.

Die Funktion ist der Hauptteil des Programms. Als Eingabe wird eine Zahl verwendet, und jede Iteration wird heruntergezählt, bis wir 1einen einzelnen Buchstaben erreichen. Der Rest der Funktion ruft die Funktion im Wesentlichen rekursiv auf, nimmt den aktuellen Buchstaben und iteriert ihn durch jede Position.

Aufgrund der Funktionsweise der Permutationsfunktion gibt es ein einziges Bit zusätzlicher Logik if($s.length-eq1){1;exit}, um Eingabezeichenfolgen mit einer Länge zu berücksichtigen 1.

Pyt , 5 Bytes

ĐᒆỤ≥Ʃ

Erläuterung:

            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)

Probieren Sie es online!