7
\$\begingroup\$

Let N = [0,1,2,...n-1] be the initial segment of the natural numbers of length n, then all permutations of N can be sorted lexicographically, starting with the identity. The index into this sorted array is known as the rank of the permutation.

For example, the permutations for n = 3 can be seen in RosettaCode, where also various algorithms for the ranking are described in different languages.

But N can also be written as a binary tree by going level by level from top to bottom and from left to right and filling the tree nodes with the elements of N keeping their natural order. For n = 5, this tree is

     0
    / \
   1   2
  / \
 3   4

Once you have the tree, you can traverse it in various ways. Here we look at the pre-order traversal. In the example, this is the sequence [0,1,3,4,2]. The rank of this sequence, seen as a permutation, is 3.

Some more examples:

 n -> traversal of binary tree as permutation -> rank
 6 -> [0, 1, 3, 4, 2, 5]                      -> 8
 8 -> [0, 1, 3, 7, 4, 2, 5, 6]                -> 222
10 -> [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]          -> 8442

TASK

Given n, construct the binary tree as described above for [0,1,2,...n-1], and return the rank of the permutation provided by the pre-order traversal of this tree. Provide evidence by showing the ranks for n = 4,5,...,9.

Scoring: This is code-golf, so the shortest code for each language wins!

Improve this question
\$\endgroup\$
1
  • 2
    \$\begingroup\$ so label them branch first and read them depth first, then count its permutation? Seems too much a pure joint of two questions \$\endgroup\$
    – l4m2
    Commented yesterday

4 Answers 4

Reset to default
10
\$\begingroup\$

Jelly, 8 4 bytes

BÞŒ¿

Try it online!

-4 because WHY exactly did I think Hamming weight was involved again??

Returns the rank 1-indexed, but the test harness converts to 0-indexed for convenience.

 Þ      Sort [1 .. n] by lexicographic comparisons of
B       their binary digits.
  Œ¿    Builtin permutation index.

Intuition:

If you label the nodes with \$[1, n]\$ instead of \$[0, n-1]\$, the labels at each "tier" of the tree all have the same length in bits:

                    1
                .../ \...
           ..../         \....
          /                   \
         10                   11
        /  \                 /  \
       /    \               /    \
      /      \             /      \
     /        \           /        \
   100        101       110        111
  /   \      /   \     /   \      /   \
1000 1001  1010 1011 1100 1101  1110 1111

and not only that, but the tree is a prefix tree of the binary representations--the direct children of every node are labeled with precisely its label with either 0 or 1 appended. Hence, lexicographic comparison of the bits will sort correctly within each tier, sort all nodes after their immediate parents, and sort all nodes before later nodes than their parents in their parents' tier.

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Python, 115 bytes

lambda n:[*permutations(range(n))].index((t:=lambda x:x<n and(x,)+t(2*x+1)+t(2*x+2)or())(0))
from itertools import*

Attempt This Online!

Python, 93 91 bytes

-2 bytes thanks to @Jonathan Allan by using the range [0, n] instead of [1, n]

lambda n:[*permutations(r:=range(n+1))].index((*sorted(r,key=bin),))
from itertools import*

Attempt This Online!

Port of Unrelated String's amazing answer

Python + SymPy, 111 88 bytes

-23 bytes thanks to @Jonathan Allan by switching to @Unrelated String's approach

lambda n:Permutation(sorted(range(n+1),key=bin)).rank()
from sympy.combinatorics import*

Attempt This Online!

Use of sympy was inspired by the program provided in A379905

Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Save two from your 93 by leaving zero in r with r:=range(n+1). This will not affect the result; it will just be less efficient. \$\endgroup\$
    – Jonathan Allan
    Commented 21 hours ago
  • 2
    \$\begingroup\$ Save 23 bytes in the +SymPy version ATO \$\endgroup\$
    – Jonathan Allan
    Commented 18 hours ago
3
\$\begingroup\$

Charcoal, 42 34 bytes

≔ＥＮ↨⊕ι²θ≔⁰ηＷ⁻θυ≔∧⊞Ｏυ⌊ι⁺×ηＬι⌕ι⌊ιηＩη

Try it online! Link is to verbose version of code. Explanation: Uses @UnrelatedString's observation.

≔ＥＮ↨⊕ι²θ

Generate the binary representations of the numbers 1..n.

≔⁰η

Start calculating the rank as if sorted.

Ｗ⁻θυ

While there are binary representations left to be ranked...

≔∧⊞Ｏυ⌊ι⁺×ηＬι⌕ι⌊ιη

... add the minimum to the list of representations that have been ranked, and then update the rank. This code was inspired by the Java code on the linked Rosetta Code page, but it's been rewritten to avoid having to sort the representations first, which in fact simplifies the code, since the number of remaining integers lower than the current integer is simply the position of the minimum representation in the list.

Ｉη

Output the final rank.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Maple, 94 bytes

proc(n)sort(convert~([$n],binary),key=String);combinat:-rankperm(convert~(%,decimal,2))-1;end;

This is @Unrelated String's nice algorithm. Take [1,...,n], convert to binary, sort in string (lex) order, convert back to decimal, and find the rank (builtin).

Improve this answer
\$\endgroup\$

Your Answer

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

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