# Finding n-th permutation without computing others

Given an array of N elements representing the permutation atoms, is there an algorithm like that:

``````function getNthPermutation( \$atoms, \$permutation_index, \$size )
``````

where `\$atoms` is the array of elements, `\$permutation_index` is the index of the permutation and `\$size` is the size of the permutation.

For instance:

``````\$atoms = array( 'A', 'B', 'C' );
// getting third permutation of 2 elements
\$perm = getNthPermutation( \$atoms, 3, 2 );

echo implode( ', ', \$perm )."n";
``````

Would print:

``````B, A
``````

Without computing every permutation until \$permutation_index ?

I heard something about factoradic permutations, but every implementation i've found gives as result a permutation with the same size of V, which is not my case.

Thanks.

65

As stated by RickyBobby, when considering the lexicographical order of permutations, you should use the factorial decomposition at your advantage.

From a practical point of view, this is how I see it:

• Perform a sort of Euclidian division, except you do it with factorial numbers, starting with `(n-1)!`, `(n-2)!`, and so on.
• Keep the quotients in an array. The `i`-th quotient should be a number between `0` and `n-i-1` inclusive, where `i` goes from `0` to `n-1`.
• This array is your permutation. The problem is that each quotient does not care for previous values, so you need to adjust them. More explicitly, you need to increment every value as many times as there are previous values that are lower or equal.

The following C code should give you an idea of how this works (`n` is the number of entries, and `i` is the index of the permutation):

``````/**
* @param n The number of entries
* @param i The index of the permutation
*/
void ithPermutation(const int n, int i)
{
int j, k = 0;
int *fact = (int *)calloc(n, sizeof(int));
int *perm = (int *)calloc(n, sizeof(int));

// compute factorial numbers
fact[k] = 1;
while (++k < n)
fact[k] = fact[k - 1] * k;

// compute factorial code
for (k = 0; k < n; ++k)
{
perm[k] = i / fact[n - 1 - k];
i = i % fact[n - 1 - k];
}

// readjust values to obtain the permutation
// start from the end and check if preceding values are lower
for (k = n - 1; k > 0; --k)
for (j = k - 1; j >= 0; --j)
if (perm[j] <= perm[k])
perm[k]++;

// print permutation
for (k = 0; k < n; ++k)
printf("%d ", perm[k]);
printf("n");

free(fact);
free(perm);
}
``````

For example, `ithPermutation(10, 3628799)` prints, as expected, the last permutation of ten elements:

``````9 8 7 6 5 4 3 2 1 0
``````
Wednesday, March 31, 2021

24
``````pseudocode:

list<set> results;
int m;
list<int> a;

// ...

a.sort();

for each i in [0..a.size]
f(i, empty_set);

// ...

void f(int ind, set current_set)
{

if (current_set.sum > m)
{
}
else
{
for (int i=ind + 1; i<a.size; ++i)
{
f(i, current_set);  // pass set by value

// if previous call reached solution, no need to continue
if (a[ind] + current_set.sum) > m
break;
}
}
}

// choose whatever "best" result you need from results, the one
// with the lowest sum or lowest number of elements
``````
Wednesday, March 31, 2021

57

First off, I would not use Standard Deviation if your data arrays have only a few entries. Use more robust statistical measures like Median Absolute Deviation (MAD), likewise you might want to test using the Median instead of the Average.

This is due to the fact that, if your "knowledge" of players' bets is limited to only a few samples, your data is going to be dominated by outliers, i.e. the player being lucky/unlucky. Statistical means may be entirely inappropriate under those circumstances and you may want to use some form of heuristic approach.

I also assume from your links, that you do not in fact intend to pick the best player but rather based on the players next set of answers "A" want to predict the correct set of answers "C" by weighing "A" based on the players' previous track record.

Of course if there were a good solution to this problem, you could make a killing on the stock market ;-) (The fact that no-one does, should be an indication as to the existence of such a solution).

But getting back to ranking the players. Your main problem is that you (have to?) take the percentage of right answers as evenly distributed from 0--100%. If the test contains multiple questions this is certainly not the case. I would look at what a completely random player "R" scores on the test and build up a relative confidence number based on how much better/worse than "R" a given real player is.

Say, for each round of the game generate a million random players and look at the distribution of scores. Use the distribution as a weight for the players' real scores. Then combine the weighted scores using MAD and calculate the Median - MAD / some number, like you already suggested.

Saturday, May 29, 2021

76

The itertools module has a useful method called permutations(). The documentation says:

itertools.permutations(iterable[, r])

Return successive r length permutations of elements in the iterable.

If r is not specified or is None, then r defaults to the length of the iterable and all possible full-length permutations are generated.

Permutations are emitted in lexicographic sort order. So, if the input iterable is sorted, the permutation tuples will be produced in sorted order.

You'll have to join your permuted letters as strings though.

``````>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> perms
``````

['stack', 'stakc', 'stcak', 'stcka', 'stkac', 'stkca', 'satck', 'satkc', 'sactk', 'sackt', 'saktc', 'sakct', 'sctak', 'sctka', 'scatk', 'scakt', 'sckta', 'sckat', 'sktac', 'sktca', 'skatc', 'skact', 'skcta', 'skcat', 'tsack', 'tsakc', 'tscak', 'tscka', 'tskac', 'tskca', 'tasck', 'taskc', 'tacsk', 'tacks', 'taksc', 'takcs', 'tcsak', 'tcska', 'tcask', 'tcaks', 'tcksa', 'tckas', 'tksac', 'tksca', 'tkasc', 'tkacs', 'tkcsa', 'tkcas', 'astck', 'astkc', 'asctk', 'asckt', 'asktc', 'askct', 'atsck', 'atskc', 'atcsk', 'atcks', 'atksc', 'atkcs', 'acstk', 'acskt', 'actsk', 'actks', 'ackst', 'ackts', 'akstc', 'aksct', 'aktsc', 'aktcs', 'akcst', 'akcts', 'cstak', 'cstka', 'csatk', 'csakt', 'cskta', 'cskat', 'ctsak', 'ctska', 'ctask', 'ctaks', 'ctksa', 'ctkas', 'castk', 'caskt', 'catsk', 'catks', 'cakst', 'cakts', 'cksta', 'cksat', 'cktsa', 'cktas', 'ckast', 'ckats', 'kstac', 'kstca', 'ksatc', 'ksact', 'kscta', 'kscat', 'ktsac', 'ktsca', 'ktasc', 'ktacs', 'ktcsa', 'ktcas', 'kastc', 'kasct', 'katsc', 'katcs', 'kacst', 'kacts', 'kcsta', 'kcsat', 'kctsa', 'kctas', 'kcast', 'kcats']

If you find yourself troubled by duplicates, try fitting your data into a structure with no duplicates like a `set`:

``````>>> perms = [''.join(p) for p in permutations('stacks')]
>>> len(perms)
720
>>> len(set(perms))
360
``````

Thanks to @pst for pointing out that this is not what we'd traditionally think of as a type cast, but more of a call to the `set()` constructor.

Tuesday, June 1, 2021

76

Just write down the five nested loops. In pseudocode,

``````for a in "ἸἼΙἹἽ"
for b in "ῇηἤήῃὴῆἡἠἢᾖἥἣῄἦᾗᾐἧᾔᾑ"
for c in "σς"
for d in "οὸόὀὄὅὂ"
for e in "ὺὖυῦύὐὑὔΰϋὕὗὓὒῢ"
emit [a,b,c,d,e]
``````

To encode these five loops with recursion, so it's good for any number of input strings, again in pseudocode,

``````g(list-of-strings) =
| case list-of-strings
| of  empty --> end-of-processing
| of  (first-string AND rest-of-strings) -->
for each ch in first-string
DO g(rest-of-strings)
``````

Now you only need to figure out where to hold each current `first-string`'s character `ch` and how to combine them all while at the `end-of-processing` (basically, your two options are a global accumulator, or an argument to a function invocation).

Saturday, July 31, 2021