Main Question

We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example

A B C D E F
1 0 0 1 0 1
1 0 0 0 0 1

is a nested subset, where the first mask tells us inclusion in the first set and the second mask tells us inclusion in the first. In this case the first set is {A,D,F} and its subset is {A,F}. I am trying to uniformly generate such subset pairs.

Some Thoughts

One could try naively to generate two random masks, use the first for the union, then the second for the intersection where it overlaps. However, this would generate subsets uniform in the initial subset, and not the pair.

Mathematically speaking this can be done by weighting each mask by the number of possible subsets it has (2^n where n is the size of the subset), randomly drawing a subset, then randomly drawing an intersection from it. However this is very challenging/inefficient to implement in practice

I am currently using C. My first idea was to find some (efficient) hash function from integers into subset pairs, however I have not had much success with this.

I am wondering if there is a superior way to do this. I don't need code (I don't have implementation issues); I am looking a conceptual approach. Any advice?

Main Question

We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example

A B C D E F
1 0 0 1 0 1
1 0 0 0 0 1

is a nested subset, where the first mask tells us inclusion in the first set and the second mask tells us inclusion in the first. In this case the first set is {A,D,F} and its subset is {A,F}. I am trying to uniformly generate such subset pairs.

Some Thoughts

One could try naively to generate two random masks, use the first for the union, then the second for the intersection where it overlaps. However, this would generate subsets uniform in the initial subset, and not the pair.

Mathematically speaking this can be done by weighting each mask by the number of possible subsets it has (2^n where n is the size of the subset), randomly drawing a subset, then randomly drawing an intersection from it. However this is very challenging/inefficient to implement in practice

My first idea was to find some (efficient) hash function from integers into subset pairs, however I have not had much success with this. I am wondering if there is a superior way to do this. I don't need code (I don't have implementation issues); I am looking a conceptual approach. Any advice?