CODEWITHSUNDEEP
data-structurestree
jjjjjj
jjjjjj

Reputation: 1172

data structure for recombining tree: parents are permutations

I am trying to create a data structure which will describe a certain type of recombining "combinations" tree (similar to here).

First, consider a tree where each node has a particular ID which is described by the sequence needed to reach the node. As an example, take a fixed list Q = [1,2,3] and arrange the possible permutations of Q into a tree T based on the sequence diagram S:

S =
        _0_
      /  |  \
     1   2   3
    /|  / \  |\
   2 3 1   3 1 2
   | | |   | | |
   3 2 3   1 2 1

Then giving each node a letter, A, B, C,... the tree T can be represented by:

T = 
        _0_
      /  |  \
     A   B   C
    /|  / \  |\
   D E F   G H I
   | | |   | | |
   J K L   M N O

where

A = {1}
B = {2}
C = {3}

D = {1,2}
E = {1,3}
F = {2,1}
G = {2,3}
H = {3,1}
I = {3,2}

J = {1,2,3}
K = {1,3,2}
L = {2,1,3}
M = {2,3,1}
N = {3,1,2}
O = {3,2,1}

Now, my goal is to come up with a data structure such that the tree that recombines in a way where nodes J and L are the same object (ie recombine), and similarly K and N recombine, and finally M and O recombine. The rule for recombining is that their parents D and F, E and H, and G and I contain the same elements, and the next element in the sequence is identical. In more detail, the rule resulting in equivalence between J and L is that their "parents" D and F are set equivalent (= {1,2}). I'm not sure how this would look for larger lists Q...

Do trees like this have a particular name? Are there any existing resources that I should look into, or any places I should start? Thanks!

Upvotes: 0

Views: 110

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59184

It's not really useful to store this graph in any kind of data structure, since everything about it can be easily calculated without any kind of storage. You could store it in any kind of directed graph data structure if you really wanted to.

As a mathematical object, I would call it the "power set lattice" of Q, and anyone who knows the words would know what I mean, since it is the complete lattice over the power set.

A picture like the ones you are drawing is the "Hasse Diagram" of the power set: https://demonstrations.wolfram.com/HasseDiagramOfPowerSets/

You could also call it the "minimal deterministic finite automaton" for the set of permutations, but that leads to algorithms that are way more complicated than anything you will need.

Upvotes: 1

jjjjjj
jjjjjj

Reputation: 1172

Following up from the edit... I suppose it might be better to represent the various combinations at each level, that is, like:

  • level 0: |Q| choose 0 nodes
  • level 1: |Q| choose 1 nodes
  • level 2: |Q| choose 2 nodes
  • level 3: |Q| choose 3 nodes

and the various interconnections between them so that there 2^(N-1) * N such edges.

Upvotes: 0

Related Questions