Найти звание слова

23

Определение

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

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

"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    

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

счет

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

Маниш Кунду
источник
Связанный.
Мартин Эндер
14
«Убедитесь, что вы начинаете считать только с 1». - Это полностью зависит от вас, чтобы иметь это требование, но учтите, что довольно часто разрешают индексирование на основе 0 или 1 для таких задач.
Джонатан Аллан
1
Да, но если вы начнете с 0, тогда вы на самом деле не отображаете исходный ранг, поэтому я решил добавить это требование.
Маниш Кунду
Полезная ссылка . Вы получите AC, если ваша программа будет запущена вовремя O(n log n)или меньше. (извините, нет Python) Моя заявка (C ++) занимает 2,53 секунды для решения теста 14.
user202729
Могу ли я сделать кортеж или список с этим словом, например, ['h', 'e', 'l', 'l', 'o']в отличие от 'hello'?
0WJYxW9FMN

Ответы:

4

Pyth , 6 байт

hxS{.p

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

объяснение

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

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

Желе , 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
Caird Coneheringaahing
источник
Отказывает слова, содержащие повторяющиеся буквы.
Маниш Кунду
@ManishKundu и Xcoder, фиксированный
Caird Coneheringaahing
К сожалению Œ¿, не работает.
user202729
Работает ли ṢŒ¿?
Esolanging Fruit
@EsolangingFruit Нет, это только результаты1
caird coinheringaahing
3

CJam , 8 байт

q_e!\a#)

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

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

Эрик Outgolfer
источник
Только что получил тот же ответ :(
Esolanging Fruit
@EsolangingFruit Вы можете опубликовать его, если хотите :-)
Эрик Аутгольфер
2

Japt , 8 10 байт

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

á â n bU Ä

Попробуй это


объяснение

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

мохнатый
источник
Обратите внимание на (необычное) требование «Убедитесь, что вы начинаете считать только с 1». В рамках OP я прокомментировал, что было бы нормально также разрешить 0.
Джонатан Аллан
1
Ах, черт возьми; Stoopid 1-индексация. Скоро обновлю, но это увеличит мой счетчик байтов на 25%.
Лохматый
2

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)

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

Гален Иванов
источник
1
23:1+/:~@~.@(A.~i.@!@#)i.]
FrownyFrog
@FrownyFrog - Хорошо использовать меня. для нахождения индекса! Благодарность!
Гален Иванов
Ссылка на TIO все еще старая версия :)
Конор О'Брайен
@ Конор О'Брайен - исправлено
Гален Иванов
Как обычно , я не успокоюсь , пока не получу решение в K , что короче , чем J один. Тем не менее, вы можете использовать тот же трюк здесь? Генерировать перестановки отсортированной входной строки (следовательно, устраняется необходимость сортировки перестановочного списка)?
Стритстер
2

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]
Dúthomhas
источник
Я сбрил несколько байтов: tio.run/…
sergiol
Больше бритья tio.run/…
sergiol
Спасибо. Когда я снова получу доступ к реальному компьютеру, я обновлюсь.
Dúthomhas
2

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
Стритстер
источник
2

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`
Кевин Круйссен
источник
2

Питон 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)

user202729
источник
Этот код действительно хорош.
Маниш Кунду
1

Шелуха , 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
Laikoni
источник
1

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]

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

Как?

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[]
Arnauld
источник
1

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>, который я всегда считал плохим лазейкой.

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


Я всегда не уверен, когда использую C и C ++, что имеет значение для общего количества байтов. Согласно программе, функции или фрагменту? ответ все еще расплывчатый (я полагаю, что это не фрагмент). Так что я собираюсь использовать самую короткую из двух возможностей.

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

#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 должен будет сказать мне, что он предпочитает удовлетворять, «написать код, чтобы принять любое слово в качестве ввода и отображать его ранг. »)

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

Dúthomhas
источник
1
Э - э ... AFAIK рассчитывать наши правила необходимо ( using namespace std, #include <algorithm> заголовки используются для определения функции в байтах и ... Нет,. main(){}Действительный C ++ (г ++) Программа на 8 байт.
user202729
Я не пытаюсь быть упрямым сопли, но я вижу представления для C и C ++ (как и другие языки) все время , что только одна функция. Я хочу окончательный ответ. По этой причине я обычно не играю в гольф на C-языках. (И я с удовольствием регольф.)
Dúthomhas
1
Даже в Python, import mathэто часто необходимо. Позвольте мне найти соответствующие мета ...
user202729
@ Dúthomhas Эти решения не требуют заголовков включает. Базовая арифметика не требует заголовка, и некоторые функции могут быть неявно объявлены и заполнены связыванием stdlib (например, putsand printf). Ваш код должен скомпилироваться и успешно работать как есть, чтобы он был действительным. См: codegolf.meta.stackexchange.com/a/10085/45941
Mego
@Mego Без объявления mainфункций не может быть запущен как есть.
user202729
0

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из-за того, как работает функция перестановок.

AdmBorkBork
источник
0

Пыть , 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)

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

mudkip201
источник