Find The Rank Of A Word

Question

Definition

The rank of a word is defined as the position of the word when all the possible permutations (or arrangements) of its letters are arranged alphabetically, like in a dictionary, no matter if the words are meaningful or not.

Let us consider these two words - "blue" and "seen". To begin with, we would write all the possible arrangements of the letters of these words in alphabetical order:

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

Now let's look from the left and find the position of the words we need. We see that the word "blue" is at the 4th position and "seen" is at 10th position. So the rank of the word "blue" is 4, and that of "seen" is 10. This is the general way of calculating the rank of a word. Make sure you start counting from 1 only.

Task

Your task is to write a code to take any word as an input and display its rank. The rank should be the output. Be careful about words containing repeated letters.

Examples

"prime" -> 94

"super" -> 93

"bless" -> 4

"speech" -> 354

"earth" -> 28

"a" -> 1

"abcd" -> 1

"baa" -> 3    

You can assume the input to be completely in lowercase and the input will only contain alphabetical characters. Also if a blank space or an invalid string is entered, you may return anything.

Scoring

This is code-golf , so the shortest code wins!

Answer 1

Python 3, 71 bytes

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

Try it online!

Answer 2

05AB1E, 5 bytes

ϐsk>

Try it online! or as a Test suite

Explanation

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

Answer 3

Gaia, 4 bytes

fuȯI

Try it online!

Answer 4

Pyth, 6 bytes

hxS{.p

Test suite.

Explanation

hxS{.p || Full program.

    .p || All the permutations of the input.
   {   || Deduplicate.
  S    || Sort.
 x     || Index of the input into this list.
h      || Increment.

Answer 5

Jelly, 5 bytes

Œ!ṢQi

Try it online! or see the test suite

How it works

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

Answer 6

Python 2, 78 bytes

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

Try it online!

---

Python 3, 73 bytes

• Thanks to Mr. Xcoder for choosing Python 3; saving five bytes.

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

Try it online!

Answer 7

CJam, 8 bytes

q_e!\a#)

Try it online!

+1 byte due to 1-indexed requirement.

Answer 8

Haskell, 56 bytes

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

Try it online!

+6 bytes because of 1-indexing requirement. :(

Answer 9

Japt, 8 10 bytes

0-indexed. Poxy, unnecessary 1-indexing, increasing my byte count by 25%!

á â n bU Ä

Test it

---

Explanation

á gets all the permutations of the input, â removes duplicates, n sorts them and b gets the index of the first occurrence of the input, U.

Answer 10

J, 28 23 bytes

-5 bytes thanks to FrownyFrog

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

How it works?

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

Try it online!

Answer 11

Husk, 6 bytes

S€(OuP

Try it online! I feel like there should be a way to drop (.

Explanation:

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

Answer 12

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 has no built-in method to compute the next lexicographic permutation, so we have to do it ourselves. But wait... it is shorter to do it with a simple recursive function that computes all possible permutations in any order.

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]

Answer 13

K (oK), 23 18 bytes

Solution:

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

Try it online!

Examples:

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

Explanation:

Generate permutations of the indices of the sorted input string, use them to index back into the input string, take the distincts, see where the original string matched, and add one.

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

Answer 14

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

Explanation:

Try it 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`

Answer 15

Python 3, 183 182 bytes

The first answer that run in polynomial time!

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)

Try it online!

Require the input to be all upper-case, because... it saves a byte.

Full program, takes input from stdin and output to stdout.

---

Variable names: (sort of ungolfed code)

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

Unfortunately, from math import factorial as f takes exactly 1 more byte.

---

(Unrelated note: I checked the Combinatorica` package of Mathematica, nothing useful, including RankPermutation)

Answer 16

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

Try it online!

+3 bytes to handle 1-indexing :/

Answer 17

APL (Dyalog Unicode), 33 bytes (SBCS)

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

Try it online!

Answer 18

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

Try it online!

Answer 19

Ruby, 49 bytes

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

Try it online!

Answer 20

JavaScript (ES6), 106 100 bytes

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]

Test cases

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

How?

P() is our recursive permutation function. But the encompassing object of P is also used to store the ranks of the permutations.

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

The wrapping code now reads as:

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

Answer 21

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

As per my asking, the code definitely need to be executable as-is. The function-only clause is basically rubbish. :-@

Thank you to those who kindly answered the question of what can be cut out for me. In the interest of valid code, I’ve avoided the popular GCC-ism of including <bits/stdc++.h>, which I have always considered a bad loophole cheat.

What follows is what remains of my original posting:

---

I am always unsure when using C and C++ what counts towards the byte total. According to Program, Function, or Snippet? the answer is still vague (as long as it isn’t a snippet, I guess). So I am going with the shortest of the two possibilities.

Here it is ungolfed with necessary headers, etc:

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

That golfs down to 230 bytes, a third of that standard boilerplate required by every C++ program. (So, I don’t feel too bad not counting it, but as I haven’t ever seen a firm complaint either way, OP will have to tell me which he prefers to satisfy “write a code to take any word as an input and display its rank.”)

I am also unsure if this satisfies “the rank should be output.”

Answer 22

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

Try it online!

Answer 23

Octave, 43 bytes

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

Try it online!

Answer 24

Perl 6, 53 bytes

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

Try it online!

Answer 25

PowerShell, 275 bytes

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

Try it online!

So, this is a bloody mess.

PowerShell doesn't have any permutations built-in, so this code uses the algorithm from here (golfed heavily), which is available under the Microsoft Limited Public License (Exhibit B on this licensing page).

The program takes input $s as a string, then the actual program starts with $b=New-Object .... We're constructing a new StringBuilder object, which is (essentially) a mutable string of characters. This will allow us to handle the permutations more easily. We then call the function n (setting $j along the way to be the length of the input string), sort with the -unique flag the output, take the .indexOf() to find the input string, and add 1 because PowerShell is zero-indexed.

The function is the main part of the program. It takes as input a number, and will each iteration count down until we reach 1 (i.e., a single letter). The rest of the function essentially recursively calls the function as well as takes the current letter and iterates it through every position.

There's a single bit of additional logic if($s.length-eq1){1;exit} to account for input strings of length 1 due to how the permutations function works.

Answer 26

Pyt, 5 bytes

ĐᒆỤ≥Ʃ

Explanation:

            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)

Try it online!