[5/2/2012] Challenge #47 [difficult]

[u/oskar_s]

If you were to generate all permutations of the first three letters of the alphabet ("a", "b" and "c") and then sort them, you would get the following list of 6 permutations:

1. abc
2. acb
3. bac
4. bca
5. cab
6. cba

As you can see, the fourth permutation in a sorted list of all the permutations of "a", "b" and "c" is "bca".

Similarly, if we wanted the 30th permutation in a sorted list of all permutations of the first five letters of the alphabet (i.e. "abcde"), you get "baedc".

Define a function f(n,p) that generates the permutation number p in a sorted list of all permutations of the n first letters of the alphabet. So, for instance:

f(3, 4) = "bca"
f(5, 30) = "baedc"
f(7, 1000) = "bdcfega"
f(8, 20000) = "dhfebagc"

Find f(11, 20000000)

---

Bonus:

Find f(20, 10¹⁸ )

[u/juanfeng]

Python

import operator

def f(c, n):
    fac = reduce(operator.mul, range(1, c))
    result = _f(n - 1, range(c), fac)
    return result

def _f(n, s, fac):
    r = s[n // fac]
    s.remove(r)
    if s:
        return [r] + _f(n % fac, s, fac // len(s))
    return [r]

# Test print for the permutations of 5 items.
items = 5
for i in range(1, reduce(operator.mul, range(1, items + 1)) + 1):
    print f(items, i)

print ''.join(chr(x + ord('a')) for x in f(11, 20000000))
print f(20, 10 ** 18)

Answer to problem:

fgbadjieckh

Output of last line:

[8, 4, 3, 10, 16, 7, 13, 6, 17, 9, 18, 12, 2, 5, 19, 1, 14, 11, 15, 0]

I used zero-oriented numbers instead of letters so I could permute any sized set.

[u/juanfeng]

Haskell

f n p = f' (p - 1) (foldr (*) 1 (take n $ 1:[1..]) ) (take n ['a'..]) n
f' _ _ xs 1 = xs
f' n fac xs s =
    item : f' nextN nextFac nextItems (s - 1)
    where item = xs !! (n `div` fac)
          nextN = n `mod` fac
          nextFac = fac `div` (s - 1)
          nextItems = filter (/= item) xs

[u/Zamarok → u/juanfeng]

Nice :) good to see more Haskellers in this subreddit.

Here's mine.

[u/robin-gvx]

http://hastebin.com/raw/tayocajixu

Translated juanfeng's solution into DV. My initial solution could only calculate the first element of the permutation.

Also, it can't handle 10^18. No idea why not. VM bug, of course, but how to fix it... no clue. (Also, I guess I should add map and pop-index to the standard library.)

[u/juanfeng → u/robin-gvx]

I literally cannot find any information about the Déjà Vu language. Do you have any links to some details?

[u/debugmonkey]

C++

Seeing how small all of the other answers are I figure there's something I'm missing, but I did at least figure out that sorting the list makes it so I don't have to actually calculate each and every permutation. Yes the code is ugly. I'm just ecstatic i got it working.

#include "stdafx.h"
#include <iostream>
#include <unordered_map>
#include <list>
#include "c:/temp/ttmath.h"
using namespace std;

typedef ttmath::UInt<6> BigInt;
class SortedPermutations
{
protected:
    unordered_map<int, BigInt> blocksize;   // total number of permutations 
    BigInt FactorialEx(int x) 
    {
        BigInt retval;
        retval = (1 == x) ? 1 :  FactorialEx(x-1) * x;
        blocksize[x] = retval / x;
        return retval;
    }
public:
    void calc(int n, BigInt TargetPos)
    {
        cout << "f(" << n << ", " << TargetPos << ") = ";
        BigInt CurrentPos = 0;
        int CurrentCol = n;
        // I don't actually care how many permutations there are. I care about block size
        if( FactorialEx(n) < TargetPos )
        {
            cout << "It's impossible to calculate you idiot. " << endl;
            return;
        }

        list <char>  AvailChars;
        for(char x = 'a'; x != ('a'+n); x++)
            AvailChars.push_back(x);
        auto itr = AvailChars.begin();
        while (CurrentPos != TargetPos && !AvailChars.empty())
        {
            if(CurrentPos + blocksize[CurrentCol] < TargetPos)
            {
                // cout << "Letter Increase!" << endl;
                CurrentPos += blocksize[CurrentCol];
                itr++;
            }
            else // block is too big, reduce size by moving to different column;
            {
                // cout << "Column Shift! Removing " << *itr << " from the avail char pool" << endl;
                cout << *itr;
                AvailChars.erase(itr);
                itr = AvailChars.begin();
                CurrentCol--;
            }
        }
        cout << endl;
    }
};

void test_hard47()
{
     SortedPermutations spObj;
     spObj.calc(3,4);
     spObj.calc(5,30);
     spObj.calc(7,1000);
     spObj.calc(8,20000);
     spObj.calc(11,20000000);
     spObj.calc(20,1000000000000000000);
     spObj.calc(26,"403291461126605635584000000");
}

and of course, output WITH BONUS!:

f(3, 4) = bca
f(5, 30) = baedc
f(7, 1000) = bdcfega
f(8, 20000) = dhfebagc
f(11, 20000000) = fgbadjieckh
f(20, 1000000000000000000) = iedkqhngrjsmcftbolpa
f(26, 403291461126605635584000000) = zyxwvutsrqponmlkjihgfedcba

It's fun seeing it work on REALLY BIG NUMBERS in milliseconds:

f(26, 403291461126605635584000000) = zyxwvutsrqponmlkjihgfedcba

... that makes me happy :)

[u/skeeto]

Essentially this Project Euler problem: Problem 24

[u/oskar_s → u/skeeto]

The bonus makes it much more difficult.

[u/bh3]

Didn't really feel like assembly for this one, so C:

char* f(long N, long P) {
    P-=1; // zero indexed.
    char table[]="abcdefghijklmnopqrstuvwxyz";
    char *s = malloc(N+1);
    s[N]='\0';
    long fact[N], i;
    fact[N-1]=1;
    for(i=N-2; i>=0; i--) fact[i]=fact[i+1]*(N-i-1);
    for(i=0; i<N; i++) {
        // if there are N characters, there are (N-1)!
        // characters per starting letter, and thus the
        // starting letter of the Pth perm. is floor(P/(N-1)!)
        // Then solve subproblem f(N-1,P-letter*(N-1)!)
        long j=0, jj=P/fact[i];
        P-=jj*fact[i];
        // lookup jj-th unused character.
        while(table[j]==' ') j++;
        while(jj-- > 0) {
            j++;
            while(table[j]==' ') j++;
        }
        s[i]=table[j];
        table[j]=' ';
    }
    return s;
}

[u/MozMorris]

Ruby

def f(n, p)
  ("a".."z").to_a[0, n].permutation.to_a.sort[p-1]
end

(it sux)