24
\$\begingroup\$

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 , so the shortest code wins!

\$\endgroup\$
7
  • \$\begingroup\$ Related. \$\endgroup\$ Jan 18, 2018 at 17:55
  • 14
    \$\begingroup\$ "Make sure you start counting from 1 only." - It's totally up to you to have this requirement, but do note that it's quite common to allow either 0 or 1 based indexing for such challenges. \$\endgroup\$ Jan 18, 2018 at 18:21
  • 1
    \$\begingroup\$ Yeah ikr but if you start from 0 then you actually aren't displaying the original rank which is why I decided to add this requirement. \$\endgroup\$ Jan 18, 2018 at 19:39
  • \$\begingroup\$ Useful link. You will get AC if your program runs in time O(n log n) or less. (sorry, no Python) My submission (C++) takes 2.53s to solve test 14. \$\endgroup\$
    – DELETE_ME
    Jan 19, 2018 at 2:20
  • \$\begingroup\$ Can I do a tuple or a list with that word, e.g. ['h', 'e', 'l', 'l', 'o'] as opposed to 'hello'? \$\endgroup\$
    – 0WJYxW9FMN
    Jan 20, 2018 at 11:55

26 Answers 26

7
\$\begingroup\$

Python 3, 71 bytes

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

Gaia, 4 bytes

fuȯI

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Fails for words containing repeated letters. \$\endgroup\$ Jan 18, 2018 at 17:14
  • \$\begingroup\$ @ManishKundu and Xcoder, fixed \$\endgroup\$ Jan 18, 2018 at 17:17
  • 1
    \$\begingroup\$ Unfortunately Œ¿ doesn't work. \$\endgroup\$
    – DELETE_ME
    Jan 19, 2018 at 2:14
  • \$\begingroup\$ Does ṢŒ¿ work? \$\endgroup\$ Jan 19, 2018 at 5:10
  • \$\begingroup\$ @EsolangingFruit No, that just outputs 1 \$\endgroup\$ Jan 19, 2018 at 7:15
3
\$\begingroup\$

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!

\$\endgroup\$
0
3
\$\begingroup\$

CJam, 8 bytes

q_e!\a#)

Try it online!

+1 byte due to 1-indexed requirement.

\$\endgroup\$
2
  • \$\begingroup\$ Just got the exact same answer :( \$\endgroup\$ Jan 19, 2018 at 5:17
  • \$\begingroup\$ @EsolangingFruit You can still post it if you want :-) \$\endgroup\$ Jan 19, 2018 at 11:13
3
\$\begingroup\$

Haskell, 56 bytes

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

Try it online!

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Note the (unusual) "Make sure you start counting from 1 only" requirement. I have commented under the OP that it would be normal to allow 0-based too. \$\endgroup\$ Jan 18, 2018 at 18:23
  • 1
    \$\begingroup\$ Ah, goddamnit; stoopid 1-indexing. Will update shortly but it'll up my byte count by 25%. \$\endgroup\$
    – Shaggy
    Jan 18, 2018 at 18:54
2
\$\begingroup\$

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!

\$\endgroup\$
7
  • 1
    \$\begingroup\$ 23: 1+/:~@~.@(A.~i.@!@#)i.] \$\endgroup\$
    – FrownyFrog
    Jan 18, 2018 at 19:07
  • \$\begingroup\$ @FrownyFrog - Good use of i. for finding the index! Thanks! \$\endgroup\$ Jan 18, 2018 at 19:17
  • \$\begingroup\$ The TIO link is still the old version :) \$\endgroup\$ Jan 18, 2018 at 19:17
  • \$\begingroup\$ @Conor O'Brien - fixed \$\endgroup\$ Jan 18, 2018 at 19:22
  • \$\begingroup\$ As usual I'm not happy until I get a solution in K that's shorter than the J one. That said, can you use the same trick here? Generate permutations of the sorted input string (therefore removing the need to sort the permutated list)? \$\endgroup\$
    – mkst
    Jan 18, 2018 at 21:46
2
\$\begingroup\$

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
\$\endgroup\$
1
2
\$\begingroup\$

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]
\$\endgroup\$
3
  • \$\begingroup\$ I shaved off some bytes: tio.run/… \$\endgroup\$
    – sergiol
    Mar 28, 2018 at 9:39
  • \$\begingroup\$ More shaving tio.run/… \$\endgroup\$
    – sergiol
    Mar 28, 2018 at 11:33
  • \$\begingroup\$ Thank you. When I get access to a real computer again I'll update. \$\endgroup\$
    – Dúthomhas
    Apr 1, 2018 at 18:14
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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`
\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ That code is really nice. \$\endgroup\$ Jan 20, 2018 at 17:00
1
\$\begingroup\$

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 :/

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 33 bytes (SBCS)

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 49 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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[]
\$\endgroup\$
1
\$\begingroup\$

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.”

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Uh... AFAIK our rules count necessary (using namespace std, #include <algorithm> headers used to define the function in bytes. And... No, main(){} is a valid C++ (g++) program at 8 bytes. \$\endgroup\$
    – DELETE_ME
    Jan 19, 2018 at 2:17
  • \$\begingroup\$ I am not trying to be an obstinate snot, but I see submissions for C and C++ (as well as other languages) all the time that are just a single function. I want a definitive answer. I typically don’t golf in C-languages for this very reason. (And I am happy to regolf.) \$\endgroup\$
    – Dúthomhas
    Jan 19, 2018 at 5:04
  • 1
    \$\begingroup\$ Even in Python, import math is often necessary. Let me find the relevant meta... \$\endgroup\$
    – DELETE_ME
    Jan 19, 2018 at 5:05
  • \$\begingroup\$ @Dúthomhas Those solutions don't require header includes. Basic arithmetic requires no header, and some functions can be implicitly declared and filled in by the linking of the stdlib (like puts and printf). Your code must compile and run successfully as-is for it to be valid. See: codegolf.meta.stackexchange.com/a/10085/45941 \$\endgroup\$
    – user45941
    Jan 19, 2018 at 5:07
  • \$\begingroup\$ @Mego Without declaration of main functions can't be run as-is. \$\endgroup\$
    – DELETE_ME
    Jan 19, 2018 at 5:09
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Octave, 43 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 53 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.