I give you Nth permutation, you give me N

Input: a sequence of uppercase letters (ASCII [65;90]) which is the Nth* lexicographical permutation of the multiset of its characters

*permutations are numbered from 0 or 1 upwards

Output: base-10 integer N

Rulez

• There might be duplicates (that's how this challenge differs from this one)
• The characters are ordered by their ASCII value
• In case of an input of length less than or equal to 1, the input is the first permutation and the result is 0 or 1 respectively
• First permutation is that in which the leftmost character has the lowest value, the rightmost character has the highest value, and the sequence of characters between the first and the last character is the first permutation of the multiset of its characters (recursive definition!)
• Shortest entry wins

Example

• Input AAB produces output 0
• Input ABA produces output 1
• Input BAA produces output 2 • Input ZZZ produces output 0
• Input DCBA produces output 23

EDIT

Extra kudos to the one who can come up with a solution which doesn't produce all permutations and then search for the input. That's some challenge.

• Hello and welcome to the site. This question is currently rather unclear. I am not really sure how the permutations are ordered. Are they lexicographically ordered? This should be defined in your question. Apr 2 '17 at 1:35
• We also have a sandbox so you can get this kind of feedback before posting to our main site. It is not mandatory to post there first, but a lot of times it is very helpful. Apr 2 '17 at 1:39
• You said 'Uppercase', zzz and dcba is not uppercase. Apr 2 '17 at 2:07
• @SIGSEGV corrected Apr 2 '17 at 2:12
• Can the output index be 1-based instead of 0-based? Apr 2 '17 at 2:51

Python 2, 69 bytes

Try it online

from itertools import*
lambda S:sorted(set(permutations(S))).index(S)

Python, 302 287 bytes

Dead Possum has already posted a short Pythonic solution, so I decided to go for the extra kudos. This solution does not generate all of the permutations. It can rapidly calculate the permutation index of a rather large string; it also handles an empty string correctly.

from math import factorial as f
from itertools import groupby as g
def p(t,b=''):
if len(t)<2:return 0
z,b=0,b or sorted(t)
for i,c in enumerate(b):
w=b[:i]+b[i+1:]
if c==t:return z+p(t[1:],w)
if i<1 or c!=b[i-1]:
n=f(len(w))
for _,v in g(w):n//=f(len(list(v)))
z+=n

Testing code:

def lexico_permute_string(s):
''' Generate all permutations of s in lexicographic order '''
a = sorted(s)
n = len(a) - 1
while True:
yield ''.join(a)
for j in range(n-1, -1, -1):
if a[j] < a[j + 1]:
break
else:
return
v = a[j]
for k in range(n, j, -1):
if v < a[k]:
break
a[j], a[k] = a[k], a[j]
a[j+1:] = a[j+1:][::-1]

def test_all(base):
for i, s in enumerate(lexico_permute_string(base)):
rank = p(s)
assert rank == i, (i, s, rank)
print('{:2} {} {:2}'.format(i, s, rank))
print(repr(base), 'ok\n')

for base in ('AAB', 'abbbbc'):
test_all(base)

def test(s):
print('{!r}\n{}\n'.format(s, p(s)))

for s in ('ZZZ', 'DCBA', 'a quick brown fox jumps over the lazy dog'):
test(s)

output

0 AAB  0
1 ABA  1
2 BAA  2
'AAB' ok

0 abbbbc  0
1 abbbcb  1
2 abbcbb  2
3 abcbbb  3
4 acbbbb  4
5 babbbc  5
6 babbcb  6
7 babcbb  7
8 bacbbb  8
9 bbabbc  9
10 bbabcb 10
11 bbacbb 11
12 bbbabc 12
13 bbbacb 13
14 bbbbac 14
15 bbbbca 15
16 bbbcab 16
17 bbbcba 17
18 bbcabb 18
19 bbcbab 19
20 bbcbba 20
21 bcabbb 21
22 bcbabb 22
23 bcbbab 23
24 bcbbba 24
25 cabbbb 25
26 cbabbb 26
27 cbbabb 27
28 cbbbab 28
29 cbbbba 29
'abbbbc' ok

'ZZZ'
0

'DCBA'
23

'a quick brown fox jumps over the lazy dog'
436629906477779191275460617121351796379337

Non-golfed version:

''' Determine the rank (lexicographic index) of a permutation
The permutation may contain repeated items

Written by PM 2Ring 2017.04.03
'''

from math import factorial as fac
from itertools import groupby

def lexico_permute_string(s):
''' Generate all permutations of s in lexicographic order '''
a = sorted(s)
n = len(a) - 1
while True:
yield ''.join(a)
for j in range(n-1, -1, -1):
if a[j] < a[j + 1]:
break
else:
return
v = a[j]
for k in range(n, j, -1):
if v < a[k]:
break
a[j], a[k] = a[k], a[j]
a[j+1:] = a[j+1:][::-1]

def perm_count(s):
''' Count the total number of permutations of sorted sequence s '''
n = fac(len(s))
for _, g in groupby(s):
n //= fac(sum(1 for u in g))
return n

def perm_rank(target, base):
''' Determine the permutation rank of string target
given the rank zero permutation string base,
i.e., the chars in base are in lexicographic order.
'''
if len(target) < 2:
return 0
total = 0
for i, c in enumerate(base):
newbase = base[:i] + base[i+1:]
elif i and c == base[i-1]:
continue
total += perm_count(newbase)

base = 'abcccdde'
print('total number', perm_count(base))

for i, s in enumerate(lexico_permute_string(base)):
rank = perm_rank(s, base)
assert rank == i, (i, s, rank)
#print('{:2} {} {:2}'.format(i, s, rank))
print('ok')

This algorithm, due to Narayana Pandita, is from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

To produce the next permutation in lexicographic order of sequence a

1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index k greater than j such that a[j] < a[k].
3. Swap the value of a[j] with that of a[k].
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

FWIW, you can see an annotated version of that function here.

FWIW, here's the inverse function.

''' Determine the permutation with given rank of the
rank zero permutation string base.
'''
if len(base) < 2:

total = 0
for i, c in enumerate(base):
if i < 1 or c != base[i-1]:
newbase = base[:i] + base[i+1:]
newtotal = total + perm_count(newbase)
if newtotal > rank:
return perm_unrank(rank - total, newbase, head + c)
total = newtotal
# Test

target = 'a quick brown fox jumps over the lazy dog'
base = ''.join(sorted(target))
rank = perm_rank(target, base)
print(target)
print(base)
print(rank)
print(perm_unrank(rank, base))

output

a quick brown fox jumps over the lazy dog
aabcdeefghijklmnoooopqrrstuuvwxyz
436629906477779191275460617121351796379337
a quick brown fox jumps over the lazy dog

And here's a function that I wrote while developing perm_unrank which shows the breakdown of the subcounts.

def counts(base):
for i, c in enumerate(base):
newbase = base[:i] + base[i+1:]
if newbase and (i < 1 or c != base[i-1]):
yield c, perm_count(newbase)
for h, k in counts(newbase):
yield c + h, k

def show_counts(base):
TAB = ' ' * 4
for s, t in counts(base):
d = len(s) - 1
print('{}{} {}'.format(TAB * d, s, t))

# Test
base = 'abccc'
print('total number', perm_count(base))
show_counts(base)

output

a 4
ab 1
abc 1
abcc 1
ac 3
acb 1
acbc 1
acc 2
accb 1
accc 1
b 4
ba 1
bac 1
bacc 1
bc 3
bca 1
bcac 1
bcc 2
bcca 1
bccc 1
c 12
ca 3
cab 1
cabc 1
cac 2
cacb 1
cacc 1
cb 3
cba 1
cbac 1
cbc 2
cbca 1
cbcc 1
cc 6
cca 2
ccab 1
ccac 1
ccb 2
ccba 1
ccbc 1
ccc 2
ccca 1
cccb 1
• Wow! Amazing solution! There are some bits of Python here I'm not familiar with that I'm going to have to go look up now to fully understand it. Well done! Apr 3 '17 at 18:40
• You can change it to z=0 and substitute in t and t[1:] where they're used (currently h and t) to save 8 bytes. Apr 4 '17 at 5:53
• Congratulations, you get the extra kudos as well! Even though Jörg Hülsermann was first, but your version is recursive so it's not the same as his. Apr 4 '17 at 10:46
• Thanks, @kyrill Now I'm wondering how to do the reverse process efficiently: produce the permutation from its index. I guess it shouldn't be too hard to modify the usual factorial-base technique used for permutations without repeats... Apr 4 '17 at 14:01
• Here's the shortest I could come up with. It returns True for values of 1 or lower, but I think with your code that should be all right? f=lambda n:n<2or n*f(n-1)
– ArBo
Jan 19 '19 at 15:40

05AB1E, 5 bytes

œêJ¹k

Uses the CP-1252 encoding. Try it online!

05AB1E, 5 bytes

œê¹Sk

Try it online!

• He beat you by 42 seconds :D Apr 2 '17 at 10:32
• @kyrill Although you still accepted the wrong answer, I beat him with my Jelly answer by 5 minutes. Apr 2 '17 at 10:34
• But that Jelly produces 1-indexed output. Rules state the permutations are numbered from 0 upwards. I gave an exception to Luis Mendo who explicitly asked for it. Apr 2 '17 at 10:37
• Apr 2 '17 at 10:37
• Yeah, giving exceptions to certain users is frowned upon. Apr 2 '17 at 10:48

PHP, 124 Bytes

$a=str_split($argn);sort($a);for($i=$j=join($a);$i<=strrev($j);$i++)$i==$argn?print+$n:(($c=count_chars)($i)!=$c($j)?:$n++); PHP, 136 Bytes foreach($t=($c=count_chars)($argn)as$k=>$v)$i=$s.=str_repeat(chr($k),$v);for(;$i<=strrev($s);$i++)$i==$argn?print+$n:($c($i)!=$t?:$n++);

Online Version

Run with

echo '<string>' | php -nR '<code>'

Calculate with factorial

Expanded Version

function f($i){return array_product(range(1,$i));} #factorial
function p($s){ return f(strlen($s))/array_product(array_map("f",count_chars($s,1))); } # factorial / divide through product of factorials for each char$a=$argn;$b="";
$r=[]; for($d=0;$a;$d++) # loop range before used chars in string
{
for($i=0;$i<strlen($a);$i++){ # loop for every char in the rest string
if($a[$i]<$a) # if char is before first char order by ascii$r[$d.$a[$i]]=p(substr_replace($a,"",$i,1)); # add range before }$a=substr($a,1); # remove first char } echo array_sum($r); # Output the range before the used permutation

Output for the string PPCG

Array
(
[0C] => 3    # in first run C is before P startposition = 3
[0G] => 3    # in first run G is before P startposition = 3+3
[1C] => 2    # in second run PC is before PP startposition = 3+3+2
[1G] => 2    # in second run PG is before PP startposition = 3+3+2+2=8
)

Online Version

• What kind of magic is this? You have bonus points for original approach, but you still produce all permutations and then search for input. Apr 2 '17 at 11:04
• @kyrill PHP can increment strings php.net/manual/en/language.operators.increment.php The logic does not search for input. It is more a comparision to the input Apr 2 '17 at 11:52
• @kyrill for 5 byte more I could replace print+$n´ with ´die("$n")´ and the loop will stop after the permutation is found. And I must add $n=0 in the loop then the cast to integer works not in this change Apr 2 '17 at 12:01 • I don't read PHP, but I think your expanded algorithm is fairly similar to mine. FWIW, I didn't notice that until after I'd written my answer. Apr 3 '17 at 11:44 • @PM2Ring It could been I could not read really your python version Apr 3 '17 at 11:59 Julia, 121 125 bytes Noncompeting, as it does not deal with duplicate letters correctly. I ported this from another language, from part of a solution to a Project Euler problem I did several years ago, and the first, 121-byte version had a bug because I had transposed the use of the permuted string and the sorted, canonical reference string. f(p)=(n=0;z=length(p)-1;s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n) For large inputs, this version uses bignums at the cost of 8 extra bytes: f(p)=(n=0;z=BigInt(length(p)-1);s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n) Ungolfed: function f(perm) nth = 0 size = length(perm) - 1 sorted = join(sort(collect(p))) for ch in sorted index = search(perm, ch) - 1 nth += factorial(size) * index perm = replace(perm, ch, "" , 1) # replace at most one copy size -= 1 end return nth end Uses a factoriadic number system, q.v. Thus, it does not produce all the permutations and for large inputs will run enormously faster than those that do. For example, the alphabet can be permuted into the rather contrived sentence "Quartz glyph job vex'd cwm finks." That sentence is the 259,985,607,122,410,643,097,474,123rd lexicographic permutation of the letters of the alphabet. (Approximately 260 septillionth permutation.) This program finds that in about 65 µs on my machine. julia> @time f("quartzglyphjobvexdcwmfinks") 0.000065 seconds (570 allocations: 19.234 KB) 259985607122410643097474122 Note that the number ends in ...122 rather than ...123 because OP requested that the permutations be numbered from 0 rather than from 1. Julia, 375 bytes I've left the indentation in for readability, but the byte count is without it. p(t,b="")=begin l=length if l(t)<2 return 0 end f=factorial g(w)=(a=[]; while w!="" s="" for c in w if c==w s="$s\$c" end end
w=replace(w,s,"")
push!(a,s)
end;a)
b=b>""?b:join(sort(collect(t)))
z=0
for(i,c) in enumerate(b)
w=b[1:i-1]*b[i+1:end]
if c==t return z+p(t[2:end],w)
elseif i>1&&c==b[i-1] continue end
n=f(l(w))
for v in g(w) n=div(n,f(l(v))) end
z+=n
end
z
end

This one is just a straight Julia port of PM 2Ring's brilliant Python solution. I got hungry, so I decided I wanted the cookie after all. It's interesting to see the similarities and the differences between the two languages. I implemented itertools.groupby (in a limited form) as g(w).

But the logic isn't mine, so go and upvote PM 2Ring's answer.

Replace f=factorial with f(x)=factorial(BigInt(x)) if you want to be able to handle large inputs like p("QUARTZGLYPHJOBVEXDCWMFINKS").

• Excellent. You get the cookie! Just fix variable names in the ungolfed version. Apr 2 '17 at 3:29
• Actually I want my cookie back. Your program returns wrong result for BAA ‒ expected 2, actual 3. Apr 2 '17 at 3:36
• @kyrill Ah, it seems I misunderstood the duplicates. In that case, I'm not sure I can see a way to do it that would avoid producing all permutations. Apr 2 '17 at 6:33
• FWIW, my answer does a similar thing, but for input strings with repeated chars. Apr 3 '17 at 11:35

MATL, 1312 11 bytes

1 byte saved thanks to G B!

tY@Xu=!Af1)

Output is 1-based.

Explanation

t      % Input string implicitly. Duplicate
Y@     % All permutations, sorted; each in a different row
Xu     % Unique rows
=      % Compare for equality, with broadcast
!      % Transpose
A      % All: true for columns that contain all entries true
f      % Find: indices of nonzero elements
1)     % Get first of those indices. Implicitly display
• Now you'll just remove the q right? Apr 2 '17 at 2:57
• @kyrill Exactly :-) Apr 2 '17 at 2:57
• And what about the S? Do you really need to sort it before the permutation?
– G B
Apr 10 '17 at 8:23
• @GB Good point, it's not needed! I forgot that the "all permutations" function sorts based on values, not on indices. Thanks! Apr 10 '17 at 9:42

Mathematica, 33 31 bytes

Changing the problem spec allowed for a 2-byte savings.

Permutations@Sort@#~Position~#&

Pure function taking a list as input and returning a nonnegative integer N in the form {{N}}.

• You can drop the -1. Apr 2 '17 at 12:54
• @MartinEnder Originally there was a requirement that the permutations be indexed from 0. Apr 2 '17 at 13:21
• @kyrill Yes, but you removed it, so Greg can save those two bytes. Apr 2 '17 at 13:23

JavaScript (ES6), 130 bytes

s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))||o.add(q.join))([...s],[])&&[...o].sort().indexOf(s)

Less golfed

s=>{
o = new Set; // use a set to avoid duplicates

// recursive function to build all permutations (no cookie for me)
p = (s, q) =>
{
y = s.map( (t,i) => // execute for each char at position i
(
t = [...s], // using t as local variable, store a copy of s
x = t.splice(i,1), // remove char from t in position i, and store in array x
p(t, q.concat(x)) // recursive call
));
if (!y) // if s was empty, I have a new permutation in q
}
// call p to enumerate all permutations
p( [...s], [] ) // convert string s to array, q starts empty

o = [...o].sort() // get elements of o and sort lexicographically
return o.indexOf(s) // return the position of the input in o
}

Test

F=

function update() {
O.textContent = F(I.value)
}

update()
<input id=I value='DCBA' oninput='update()'>
<pre id=O></pre>

• Well, you don't get a cookie, but you get extra credit for implementing your own function to generate permutations ;-) Apr 4 '17 at 10:39

q_e!\a#

Try it online!

Pyth, 5 bytes

xS{.p

Online interpreter

Takes quoted input.

• @LeakyNun It doesn't work. Apr 30 '17 at 10:50
• @LeakyNun Input 'BAA' must return 2 since it's zero-indexed, but it returns 4 instead. Apr 30 '17 at 10:52

Scala, 40 bytes

s=>s.permutations.toSeq.sorted indexOf s

To use it, assign this function to a variable:

val f:(String=>Int)=s=>s.permutations.toSeq.sorted indexOf s
println(f("BAA"))

Try it online at ideone

Unfortunately, permutations returns an iterator, which doesn't have a sorted method, so it has to be converted to a Seq

C++, 96 bytes

We can make full use of the standard library here. The list of letters is passed as start/end iterators in standard C++ style.

#include<algorithm>
int f(char*a,char*z){int i=0;while(std::prev_permutation(a,z))++i;return i;}

We don't need to generate all permutations - since we have a transformation from one permutation to its predecessor, we simply count how many iterations it takes to reach the zeroth value.

Test program:

#include<cstring>
#include<iostream>
int main(int argc, char **argv)
{
while (*++argv)
std::cout << *argv << ": "
<< f(*argv, *argv+std::strlen(*argv)) << std::endl;
}

Test results:

BAA: 0
BAA: 1
BAA: 2
ZZZ: 0
DCBA: 23
: 0
• That's an original approach. Extra kudos to you too! Apr 10 '17 at 9:10

0-indexed

ñ á bU

Try it

Jelly, 5 bytes

Œ!QṢi

Try it online!

1-indexed output.

• @downvoter This post is perfectly valid. Apr 13 '17 at 13:16

Ruby, 50 bytes

I expected this to be shorter. I wouldn't have added the sort if the docs didn't say "the implementation makes no guarantees about the order in which the permutations are yielded."

->x{x.chars.permutation.map{|v|v*""}.sort.index x}