Temukan Pangkat Kata

23

Definisi

Pangkat kata didefinisikan sebagai posisi kata ketika semua kemungkinan permutasi (atau pengaturan) huruf-hurufnya diatur secara alfabet, seperti dalam kamus, tidak peduli apakah kata-katanya bermakna atau tidak.

Mari kita perhatikan dua kata ini - "biru" dan "terlihat". Untuk memulainya, kami akan menulis semua susunan huruf yang mungkin dari kata-kata ini dalam urutan abjad:

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

Sekarang mari kita lihat dari kiri dan temukan posisi kata-kata yang kita butuhkan. Kita melihat bahwa kata "biru" berada di posisi ke-4 dan "terlihat" berada di posisi ke-10. Jadi pangkat kata "biru" adalah 4, dan "terlihat" adalah 10. Ini adalah cara umum untuk menghitung pangkat kata. Pastikan Anda mulai menghitung dari 1 saja.

Tugas

Tugas Anda adalah menulis kode untuk mengambil kata apa pun sebagai input dan menampilkan peringkatnya. Pangkat harus menjadi output. Hati-hati dengan kata-kata yang mengandung huruf berulang.

Contohnya

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

Anda dapat menganggap input sepenuhnya dalam huruf kecil dan input hanya akan berisi karakter alfabet . Juga jika ruang kosong atau string tidak valid dimasukkan, Anda dapat mengembalikan apa pun.

Mencetak gol

Ini adalah , jadi kode terpendek menang!

Manish Kundu
sumber
Terkait
Martin Ender
14
"Pastikan kamu mulai menghitung dari 1 saja." - Ini sepenuhnya terserah Anda untuk memiliki persyaratan ini, tetapi perhatikan bahwa cukup umum untuk memungkinkan pengindeksan berbasis 0 atau 1 untuk tantangan seperti itu.
Jonathan Allan
1
Ya ikr tetapi jika Anda mulai dari 0 maka Anda sebenarnya tidak menampilkan peringkat asli yang mengapa saya memutuskan untuk menambahkan persyaratan ini.
Manish Kundu
Tautan yang bermanfaat . Anda akan mendapatkan AC jika program Anda berjalan dalam waktu O(n log n)atau kurang. (maaf, tidak ada Python) Kiriman saya (C ++) membutuhkan 2,53 untuk menyelesaikan tes 14.
user202729
Bisakah saya membuat tuple atau daftar dengan kata itu, misalnya ['h', 'e', 'l', 'l', 'o']sebagai lawan 'hello'?
0WJYxW9FMN

Jawaban:

7

Python 3 , 71 byte

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

Cobalah online!

Dennis
sumber
6

05AB1E , 5 byte

ϐsk>

Cobalah online! atau sebagai Test suite

Penjelasan

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

Pyth , 6 byte

hxS{.p

Suite uji.

Penjelasan

hxS {.p || Program lengkap.

    .p || Semua permutasi dari input.
   {|| Deduplicate.
  S || Menyortir.
 x || Indeks input ke dalam daftar ini.
h || Kenaikan.
Tuan Xcoder
sumber
3

Jelly , 5 byte

Œ!ṢQi

Cobalah online! atau lihat test suite

Bagaimana itu bekerja

Œ!Ṣ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 coinheringaahing
sumber
Gagal kata-kata yang mengandung huruf berulang.
Manish Kundu
@ManishKundu dan Xcoder, diperbaiki
caird coinheringaahing
Sayangnya Œ¿tidak berhasil.
user202729
Apakah ṢŒ¿bekerja?
Buah Esolanging
@EsolangingFruit Tidak, itu hanya keluaran1
caird coinheringaahing
3

Python 2 , 78 byte

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

Cobalah online!


Python 3 , 73 byte

  • Terima kasih kepada Tn. Xcoder karena memilih Python 3; menghemat lima byte.
lambda s:-~sorted({*permutations(s)}).index((*s,))
from itertools import*

Cobalah online!

Jonathan Frech
sumber
3

CJam , 8 byte

q_e!\a#)

Cobalah online!

+1 byte karena persyaratan 1-diindeks.

Erik the Outgolfer
sumber
Baru saja mendapat jawaban yang sama persis :(
Esolanging Fruit
@EsolangingFruit Anda masih dapat mempostingnya jika Anda mau :-)
Erik the Outgolfer
3

Haskell , 56 byte

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

Cobalah online!

+6 byte karena persyaratan pengindeksan 1. :(

benar-benar manusiawi
sumber
2

Japt , 8 10 byte

Diindeks 0. Poxy, pengindeksan 1 yang tidak perlu, meningkatkan jumlah byte saya sebesar 25%!

á â n bU Ä

Menguji


Penjelasan

ámendapatkan semua permutasi input, âmenghapus duplikat, nmengurutkannya dan bmendapatkan indeks kemunculan input pertama U,.

Shaggy
sumber
Perhatikan persyaratan (tidak biasa) "Pastikan Anda mulai menghitung dari 1 saja". Saya telah berkomentar di bawah OP bahwa itu akan normal untuk memungkinkan berbasis 0 juga.
Jonathan Allan
1
Ah, sial; pengindeksan 1 jongkok. Akan memperbarui segera tetapi itu akan meningkatkan jumlah byte saya sebesar 25%.
Shaggy
2

J , 28 23 byte

-5 byte berkat FrownyFrog

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

Bagaimana itu bekerja?

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

Cobalah online!

Galen Ivanov
sumber
1
23:1+/:~@~.@(A.~i.@!@#)i.]
FrownyFrog
@FrownyFrog - Penggunaan i. untuk menemukan indeks! Terima kasih!
Galen Ivanov
TIO masih merupakan versi lama :)
Conor O'Brien
@Conor O'Brien - diperbaiki
Galen Ivanov
Seperti biasa saya tidak senang sampai saya mendapatkan solusi dalam K yang lebih pendek dari J satu. Yang mengatakan, dapatkah Anda menggunakan trik yang sama di sini? Hasilkan permutasi dari string input yang diurutkan (karena itu menghilangkan kebutuhan untuk mengurutkan daftar yang diijinkan)?
streetster
2

Tcl, 196 byte

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 tidak memiliki metode bawaan untuk menghitung permutasi leksikografis berikutnya, jadi kita harus melakukannya sendiri. Tapi tunggu ... lebih pendek melakukannya dengan fungsi rekursif sederhana yang menghitung semua permutasi yang memungkinkan dalam urutan apa pun.

Tidak Disatukan:

# 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
sumber
Saya mencukur beberapa byte: tio.run/…
sergiol
Lebih mencukur tio.run/...
sergiol
Terima kasih. Ketika saya mendapatkan akses ke komputer nyata lagi saya akan memperbarui.
Dúthomhas
2

K (oK) , 23 18 byte

Larutan:

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

Cobalah online!

Contoh:

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

Penjelasan:

Hasilkan permutasi dari indeks string input yang diurutkan, gunakan mereka untuk mengindeks kembali ke string input, ambil perbedaan, lihat di mana string asli cocok, dan tambahkan satu.

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
streetster
sumber
2

Java 8, 211 byte

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

Penjelasan:

Cobalah 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`
Kevin Cruijssen
sumber
2

Python 3 , 183 182 byte

Jawaban pertama yang dijalankan dalam waktu 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)

Cobalah online!

Membutuhkan input untuk semua huruf besar, karena ... menghemat satu byte.

Program lengkap, mengambil input dari stdindan output ke stdout.


Nama-nama variabel: (semacam kode yang tidak dipisahkan)

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

Sayangnya, from math import factorial as fdibutuhkan tepat 1 byte lagi.


(Catatan yang tidak terkait: Saya memeriksa Combinatorica`paket Mathematica, tidak ada yang berguna, termasuk RankPermutation)

pengguna202729
sumber
Kode itu sangat bagus.
Manish Kundu
1

Sekam , 6 byte

S€(OuP

Cobalah online! Saya merasa harus ada cara untuk menjatuhkan (.

Penjelasan:

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

Bersih , 113 111 byte

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

Cobalah online!

+3 byte untuk menangani pengindeksan 1: /

Suram
sumber
1

Python 3 , 105 104 103 byte

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

Cobalah online!

Dennis
sumber
1

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]

Uji kasus

Bagaimana?

P () adalah fungsi permutasi rekursif kami. Tetapi objek P yang melingkupi juga digunakan untuk menyimpan peringkat permutasi.

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

Kode pembungkus sekarang terbaca sebagai:

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
sumber
1

C ++, 230 byte

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

Sesuai permintaan saya, kode pasti harus dapat dieksekusi apa adanya. Klausa fungsi-satunya pada dasarnya adalah sampah. : - @

Terima kasih kepada mereka yang dengan ramah menjawab pertanyaan tentang apa yang bisa cocok untuk saya. Untuk kepentingan kode yang valid , saya telah menghindari GCC-isme yang populer termasuk <bits / stdc ++. H>, yang saya selalu anggap sebagai cheat loophole yang buruk.

Berikut ini apa yang tersisa dari postingan asli saya:


Saya selalu tidak yakin ketika menggunakan C dan C ++ apa yang diperhitungkan terhadap total byte. Menurut Program, Fungsi, atau Cuplikan? jawabannya masih kabur (asalkan bukan potongan, saya kira). Jadi saya pergi dengan dua kemungkinan terpendek.

Ini dia ungolfed dengan header yang diperlukan, dll:

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

Itu golf turun ke 230 byte, sepertiga dari pelat standar yang dibutuhkan oleh setiap program C ++. (Jadi, saya merasa tidak terlalu buruk untuk tidak menghitungnya, tetapi karena saya belum pernah melihat keluhan yang tegas, OP harus memberi tahu saya mana yang dia inginkan untuk memuaskan “tulis kode untuk menerima kata sebagai masukan dan tampilkan peringkatnya. ")

Saya juga tidak yakin apakah ini memuaskan "peringkat harus menjadi output."

Dúthomhas
sumber
1
Uh ... AFAIK aturan kami menghitung perlu ( using namespace std, #include <algorithm> tajuk yang digunakan untuk mendefinisikan fungsi dalam byte. Dan ... Tidak, main(){}adalah program C ++ (g ++) yang valid pada 8 byte.
user202729
Saya tidak mencoba menjadi ingot yang ngotot, tetapi saya melihat kiriman untuk C dan C ++ (serta bahasa lain) sepanjang waktu yang hanya merupakan fungsi tunggal. Saya ingin jawaban yang pasti. Saya biasanya tidak bermain golf dalam bahasa C karena alasan ini. (Dan saya senang untuk mengatur kembali.)
Dúthomhas
1
Bahkan dengan Python, import mathseringkali diperlukan. Biarkan saya menemukan meta yang relevan ...
user202729
@ Dúthomhas Solusi itu tidak memerlukan sundulan. Aritmatika dasar tidak memerlukan tajuk, dan beberapa fungsi dapat secara implisit dideklarasikan dan diisi oleh tautan dari stdlib (seperti putsdan printf). Kode Anda harus dikompilasi dan dijalankan dengan sukses apa adanya agar valid. Lihat: codegolf.meta.stackexchange.com/a/10085/45941
Mego
@Mego Tanpa deklarasi mainfungsi tidak dapat dijalankan apa adanya.
user202729
0

Perl 5 , 98 + 3 ( -pF) = 101 byte

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

Cobalah online!

Xcali
sumber
0

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

Cobalah online!

Jadi, ini berantakan sekali.

PowerShell tidak memiliki permutasi bawaan, jadi kode ini menggunakan algoritme dari sini (golf sangat), yang tersedia di bawah Lisensi Publik Terbatas Microsoft ( Bukti B pada halaman lisensi ini).

Program mengambil input $ssebagai string, lalu program yang sebenarnya dimulai dengan $b=New-Object .... Kami sedang membangun objek StringBuilder baru , yang (pada dasarnya) adalah string karakter yang bisa berubah. Ini akan memungkinkan kita untuk menangani permutasi dengan lebih mudah. Kami kemudian memanggil fungsi n(pengaturan $jsepanjang panjang string input), sortdengan -uflag nique output, ambil .indexOf()untuk menemukan string input, dan tambahkan 1karena PowerShell diindeks nol.

Fungsi adalah bagian utama dari program. Dibutuhkan sebagai input nomor, dan masing-masing iterasi akan dihitung mundur sampai kita mencapai 1(yaitu, satu huruf). Sisa dari fungsi tersebut pada dasarnya memanggil fungsi secara berulang serta mengambil huruf saat ini dan beralih ke setiap posisi.

Ada sedikit logika tambahan if($s.length-eq1){1;exit}untuk menjelaskan panjang input string 1karena cara fungsi permutasi bekerja.

AdmBorkBork
sumber
0

Pyt , 5 byte

ĐᒆỤ≥Ʃ

Penjelasan:

            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)

Cobalah online!

mudkip201
sumber