Calculate rang and derang of ordering of subsets

Joined
Feb 6, 2024
Messages
2
Reaction score
0
We have all the subsets of the set {1, 2, ..., n} for some natural number n. We define the ordering of these subsets as follows:

  • The empty set has rank 0.
  • Following are all the sets whose smallest element is 1. These are first ordered by cardinality, and sets of the same cardinality are then ordered lexicographically.
  • Following are all the sets whose smallest element is 2. These are first ordered by cardinality, and sets of the same cardinality are then ordered lexicographically. ...
  • Following are all the sets whose smallest element is n-1. These are first ordered by cardinality, and sets of the same cardinality are then ordered lexicographically.
  • Following are all the sets whose smallest element is n. Thus, at the last position is the set {n}.
Example: n=4 Ordering of subsets: ∅, {1}, {1, 2}, {1, 3}, {1, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2, 3, 4}, {2}, {2, 3}, {2, 4}, {2, 3, 4}, {3}, {3, 4}, {4}

  1. Write a method rang that returns the rank of a given subset according to the above ordering. You can use the function kSubsetLexRang(subset, k, n), which returns the rank of the k-subset of a set with n elements in lexicographic order.
  2. Write a method derang that, given integers r and n, returns a subset of the set {1, 2, ..., n} whose rank according to the above ordering is r. You can use the function kSubsetLexRang(r, k, n), which returns the derangement of the k-subset of a set with n elements in lexicographic order.
I can't find any connection between the lexicographical ordering of the k-subsets of the n-tuple and this ordering. Any idea? Similarly with derang, I have no idea how to construct the corresponding set.
 
Joined
Sep 21, 2022
Messages
122
Reaction score
15
function C(n,r) is the combination function

I suggest handling {} rank 0 as a seperate piece of logic.

This approach is a bit messy and only tested for N=4

The reverse, going from a rank to a subset, would use WHILE loops instead of FOR loops, and the same math.

Code:
FUNCTION INSIDE_RANK(S,N)
'example,
' S[0]=2
' LEN(S)=3
' N=9
' [2,3,4] ranks 0
' [2,3,5] ranks 1
' [2,8,9] ranks last
LOCAL I,J,K,R
K=LEN(S)-1
R=0
FOR I=1 TO LEN(S)-1
  K-=1
  FOR J=S[I-1]+1 TO S[I]-1
    R+=C(N-J,K)
INSIDE_RANK=R

FUNCTION SUBSETS_MIN(X,N)
'Count of subsets that have X as their lowest member.
SUBSETS_MIN=2^(N-X)

FUNCTION SUBSETS_LEN(X,Y,N)
'Count of subsets that have X their lowest member,
'and Y as their length.
SUBSETS_LEN=C(N-X,Y-1)

FUNCTION RANK(S,N)
LOCAL I,R
R=0
FOR I=1 TO S[0]-1
  R+=SUBSETS_MIN(I,N)
FOR I=1 TO LEN(S)-1
  R+=SUBSETS_LEN(S[0],I,N)
R+=INSIDE_RANK(S,N)
RANK=R+1
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,780
Messages
2,569,611
Members
45,286
Latest member
ChristieSo

Latest Threads

Top