Определение

Ранг слова определяется как позиция слова, когда все возможные перестановки (или расположения) его букв расположены в алфавитном порядке, как в словаре, независимо от того, являются ли слова значимыми или нет.

Давайте рассмотрим эти два слова - «синий» и «увиденный». Для начала, мы бы написали все возможные расположения букв этих слов в алфавитном порядке:

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

Теперь давайте посмотрим слева и найдем расположение нужных нам слов. Мы видим, что слово «синий» находится на 4-й позиции, а «видимый» - на 10-й. Таким образом, ранг слова «синий» равен 4, а ранг «увиденного» - 10. Это общий способ вычисления ранга слова. Убедитесь, что вы начинаете считать только с 1.

задача

Ваша задача - написать код, который будет принимать любое слово и отображать его рейтинг. Ранг должен быть выходным. Будьте осторожны со словами, содержащими повторяющиеся буквы.

Примеры

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

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

счет

Это код-гольф , поэтому выигрывает самый короткий код!

Gaia , 4 байта

fuȯI

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

Python 3 , 71 байт

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

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

05AB1E , 5 байтов

ϐsk>

Попробуйте онлайн! или как тестовый набор

объяснение

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

hxS{.p

Тестирование.

объяснение

hxS {.p || Полная программа.

    .p || Все перестановки ввода.
   {|| Дедуплицировать.
  S || Сортировать.
 х || Индекс ввода в этот список.
ч || Increment.

Желе , 5 байт

Œ!ṢQi

Попробуйте онлайн! или посмотрите набор тестов

Как это работает

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

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

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

Python 3 , 73 байта

• Спасибо мистеру Xcoder за выбор Python 3; экономя пять байтов.

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

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

CJam , 8 байт

q_e!\a#)

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

+1 байт из-за 1-индексированного требования.

Haskell , 56 байт

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

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

+6 байт из-за требования 1-индексации. :(

Japt , 8 10 байт

0 индексированные. Poxy, ненужная 1-индексация, увеличивая мой счетчик байтов на 25%!

á â n bU Ä

Попробуй это

объяснение

áполучает все перестановки входных, âудаляет дубликаты, nсортирует их и bполучает индекс первого вхождения входа, U.

J , 28 23 байта

-5 байт благодаря FrownyFrog

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

Как это работает?

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

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

Tcl, 196 байт

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 не имеет встроенного метода для вычисления следующей лексикографической перестановки, поэтому мы должны сделать это сами. Но подождите ... это короче сделать это с помощью простой рекурсивной функции, которая вычисляет все возможные перестановки в любом порядке.

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 (ок) , 23 18 байт

Решение:

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

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

Примеры:

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

Объяснение:

Генерируйте перестановки индексов отсортированной входной строки, используйте их для индексации входной строки, возьмите отличия, посмотрите, где совпадает исходная строка, и добавьте один.

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

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

Объяснение:

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

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`

Питон 3 , 183 182 байта

Первый ответ, который запускается за полиномиальное время!

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)

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

Все входные данные должны быть прописными, потому что ... они сохраняют байт.

Полная программа, принимает данные от stdinи до stdout.

Имена переменных: (вид неопрятного кода)

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

К сожалению, from math import factorial as fзанимает ровно 1 байт.

(Несвязанное примечание: я проверил Combinatorica`пакет Mathematica, ничего полезного, в том числе RankPermutation)

Шелуха , 6 байт

S€(OuP

Попробуйте онлайн! Я чувствую, что должен быть способ бросить (.

Объяснение:

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

чистый , 113 111 байт

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

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

+3 байта для обработки 1-индексации: /

APL (Dyalog Unicode) , 33 байта (SBCS)

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

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

Python 3 , 105 104 103 байта

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

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

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

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

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

JavaScript (ES6), 106 100 байт

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]

Контрольные примеры

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

Как?

P () - наша рекурсивная функция перестановки. Но охватывающий объект P также используется для хранения рангов перестановок.

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

Код переноса теперь читается как:

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

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

Согласно моему требованию, код должен быть исполняемым как есть. Предложение «только функция» в основном является мусором. : - @

Спасибо тем, кто любезно ответил на вопрос, что можно вырезать для меня. В интересах действительных кода я избегал популярного GCC-изизма, включающего <bits / stdc ++. H>, который я всегда считал плохим лазейкой.

Далее следует то, что осталось от моей первоначальной публикации:

Здесь он не имеет необходимых заголовков и т. Д.

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

Это сокращает до 230 байт, треть этого стандартного шаблона требуется каждый программой C ++. (Итак, я не чувствую себя слишком плохо, не считая ее, но поскольку я никогда не видел какой-либо твердой жалобы, OP должен будет сказать мне, что он предпочитает удовлетворять, «написать код, чтобы принять любое слово в качестве ввода и отображать его ранг. »)

Я также не уверен, удовлетворяет ли это «ранг должен быть выведен».

Perl 5 , 98 + 3 ( -pF) = 101 байт

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

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

Октава , 43 байта

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

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

Perl 6 , 53 байта

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

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

PowerShell , 275 байт

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

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

Итак, это кровавый беспорядок.

PowerShell не имеет встроенных перестановок, поэтому в этом коде используется алгоритм отсюда (интенсивно играющий в гольф), который доступен в рамках ограниченной общественной лицензии Microsoft ( Приложение B на этой странице лицензирования).

Программа принимает ввод $sв виде строки, то фактическая программа начинается с $b=New-Object .... Мы создаем новый объект StringBuilder , который является (по сути) изменяемой строкой символов. Это позволит нам легче обрабатывать перестановки. Затем мы вызываем функцию n(устанавливая $jвдоль длины длину входной строки), sortс -uфлагом nique на выходе, берем.indexOf() чтобы найти входную строку и добавляем, 1потому что PowerShell имеет нулевую индексацию.

Функция является основной частью программы. Он принимает в качестве входных данных число, и каждая итерация будет вести обратный отсчет, пока мы не достигнем 1(т. Е. Одной буквы) Остальная часть функции по существу рекурсивно вызывает функцию, а также берет текущую букву и повторяет ее через каждую позицию.

Есть один бит дополнительной логики if($s.length-eq1){1;exit}для учета входных строк длины 1из-за того, как работает функция перестановок.

Пыть , 5 байт

ĐᒆỤ≥Ʃ

Объяснение:

            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)

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