20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic Apr 2 '17 at 1:35
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic Apr 2 '17 at 1:39
  • \$\begingroup\$ You said 'Uppercase', zzz and dcba is not uppercase. \$\endgroup\$ – Matthew Roh Apr 2 '17 at 2:07
  • \$\begingroup\$ @SIGSEGV corrected \$\endgroup\$ – kyrill Apr 2 '17 at 2:12
  • \$\begingroup\$ Can the output index be 1-based instead of 0-based? \$\endgroup\$ – Luis Mendo Apr 2 '17 at 2:51

16 Answers 16

0
\$\begingroup\$

Jelly, 5 bytes

Œ!QṢi

Try it online!

1-indexed output.

\$\endgroup\$
  • \$\begingroup\$ @downvoter This post is perfectly valid. \$\endgroup\$ – Erik the Outgolfer Apr 13 '17 at 13:16
5
\$\begingroup\$

Python 2, 69 bytes

Try it online

from itertools import*
lambda S:sorted(set(permutations(S))).index(S)
\$\endgroup\$
4
\$\begingroup\$

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[0]: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
    head, newtarget = target[0], target[1:]
    for i, c in enumerate(base):
        newbase = base[:i] + base[i+1:]
        if c == head:
            return total + perm_rank(newtarget, newbase)
        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')

About lexico_permute_string

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.

def perm_unrank(rank, base, head=''):
    ''' Determine the permutation with given rank of the 
        rank zero permutation string `base`.
    '''
    if len(base) < 2:
        return head + ''.join(base)

    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
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – David Conrad Apr 3 '17 at 18:40
  • \$\begingroup\$ You can change it to z=0 and substitute in t[0] and t[1:] where they're used (currently h and t) to save 8 bytes. \$\endgroup\$ – David Conrad Apr 4 '17 at 5:53
  • \$\begingroup\$ 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. \$\endgroup\$ – kyrill Apr 4 '17 at 10:46
  • \$\begingroup\$ 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... \$\endgroup\$ – PM 2Ring Apr 4 '17 at 14:01
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – ArBo Jan 19 at 15:40
3
\$\begingroup\$

05AB1E, 5 bytes

œêJ¹k

Uses the CP-1252 encoding. Try it online!

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

05AB1E, 5 bytes

œê¹Sk

Try it online!

Independently discovered from Adnan's answer.

\$\endgroup\$
  • \$\begingroup\$ He beat you by 42 seconds :D \$\endgroup\$ – kyrill Apr 2 '17 at 10:32
  • \$\begingroup\$ @kyrill Although you still accepted the wrong answer, I beat him with my Jelly answer by 5 minutes. \$\endgroup\$ – Erik the Outgolfer Apr 2 '17 at 10:34
  • \$\begingroup\$ 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. \$\endgroup\$ – kyrill Apr 2 '17 at 10:37
  • \$\begingroup\$ @kyrill You have agreed that 1-indexed output is acceptable though. \$\endgroup\$ – Erik the Outgolfer Apr 2 '17 at 10:37
  • 6
    \$\begingroup\$ Yeah, giving exceptions to certain users is frowned upon. \$\endgroup\$ – Erik the Outgolfer Apr 2 '17 at 10:48
3
\$\begingroup\$

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[0]) # 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

\$\endgroup\$
  • \$\begingroup\$ What kind of magic is this? You have bonus points for original approach, but you still produce all permutations and then search for input. \$\endgroup\$ – kyrill Apr 2 '17 at 11:04
  • \$\begingroup\$ @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 \$\endgroup\$ – Jörg Hülsermann Apr 2 '17 at 11:52
  • \$\begingroup\$ @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 \$\endgroup\$ – Jörg Hülsermann Apr 2 '17 at 12:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – PM 2Ring Apr 3 '17 at 11:44
  • 1
    \$\begingroup\$ @PM2Ring It could been I could not read really your python version \$\endgroup\$ – Jörg Hülsermann Apr 3 '17 at 11:59
3
\$\begingroup\$

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[1] 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[1] 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").

\$\endgroup\$
  • \$\begingroup\$ Excellent. You get the cookie! Just fix variable names in the ungolfed version. \$\endgroup\$ – kyrill Apr 2 '17 at 3:29
  • 1
    \$\begingroup\$ Actually I want my cookie back. Your program returns wrong result for BAA ‒ expected 2, actual 3. \$\endgroup\$ – kyrill Apr 2 '17 at 3:36
  • \$\begingroup\$ @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. \$\endgroup\$ – David Conrad Apr 2 '17 at 6:33
  • \$\begingroup\$ FWIW, my answer does a similar thing, but for input strings with repeated chars. \$\endgroup\$ – PM 2Ring Apr 3 '17 at 11:35
3
\$\begingroup\$

MATL, 13 12 11 bytes

1 byte saved thanks to G B!

tY@Xu=!Af1)

Output is 1-based.

Try it online! Or verify all test cases.

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
\$\endgroup\$
  • \$\begingroup\$ Now you'll just remove the q right? \$\endgroup\$ – kyrill Apr 2 '17 at 2:57
  • \$\begingroup\$ @kyrill Exactly :-) \$\endgroup\$ – Luis Mendo Apr 2 '17 at 2:57
  • 1
    \$\begingroup\$ And what about the S? Do you really need to sort it before the permutation? \$\endgroup\$ – G B Apr 10 '17 at 8:23
  • \$\begingroup\$ @GB Good point, it's not needed! I forgot that the "all permutations" function sorts based on values, not on indices. Thanks! \$\endgroup\$ – Luis Mendo Apr 10 '17 at 9:42
2
\$\begingroup\$

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

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

JavaScript (ES6), 130 bytes

s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||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[0]) // if s was empty, I have a new permutation in q
      o.add( q.join('')) // convert to string and add to output set 
  }
  // 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=
s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||o.add(q.join``))([...s],[])&&[...o].sort().indexOf(s)

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

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

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

CJam, 7 bytes

q_e!\a#

Try it online!

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

Pyth, 5 bytes

xS{.p

Online interpreter

Takes quoted input.

\$\endgroup\$
  • \$\begingroup\$ @LeakyNun It doesn't work. \$\endgroup\$ – Erik the Outgolfer Apr 30 '17 at 10:50
  • \$\begingroup\$ @LeakyNun Input 'BAA' must return 2 since it's zero-indexed, but it returns 4 instead. \$\endgroup\$ – Erik the Outgolfer Apr 30 '17 at 10:52
1
\$\begingroup\$

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

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

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
\$\endgroup\$
  • \$\begingroup\$ That's an original approach. Extra kudos to you too! \$\endgroup\$ – kyrill Apr 10 '17 at 9:10
1
\$\begingroup\$

Japt, 6 bytes

0-indexed

ñ á bU

Try it

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

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}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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