[<<][staapl][>>][..]
Mon Aug 27 23:39:23 CEST 2007

legal permutations


it looks like a more interesting approach is to start with operations
that are legal and invertible, and find their closure.

the difference with baker's machine is that i'm trying to use only one
root. hmm.. there has to be a way to see if a permutation is legal..

why is (2 3 5) not legal. because 5 gets the value of 2, which points
to 5. so a condition is that a register x cannot receive the contents
of a register y if x is in a subtree of y.

in (5 3 2) none such assignment happens.
- 5 is not a subtree of 3
- 2 is not a subtree of 2
- 3 is not a subtree of 5

'subtree of' can be computed by comparing box addresses

    [1]
   [2|3]
[4|5] [6|7]

        [1]
      [10|11]
[100|101] [110|111]

a is a subtree of b if b matches the head of a.

this way, no circular refs can be introduced. instead of thinking
about cons cells, think of binary trees. it indeed does not make sense
to swap nodes if one node is a subtree of another node.

what about enumerating all legal binary permutations on an infinite
binary tree?


()           identity

(2 3)

(2 6)  (2 7)
(3 4)  (3 5)

(4 6)  (4 7)
(5 6)  (5 7)

(2 12) (2 13) (2 14) (2 15)
(3 8)  (3 9)  (3 10) (3 11)
(4 12) (4 13) (4 14) (4 15)
(5 12) (5 13) (5 14) (5 15)
(6 8)  (6 9)  (6 10) (6 11)
...



back from tree rotations, which are not general enough...

in binary

()

(10 11)

(10 110,111)  (11 100,101)

(100,101 110,111)


back to numbers

level (bits)
1                /
2                (2 3)
3                (2 6,7) (3 4,5)
                 (4 5,6,7) (5 6,7) (6 7)
4                (2 12,13,14,15) (3 8,9,10,11)
                 (5 8,9,12,13,14,15)

it's quite hard to specify without exclusion statements..

but i guess i got what i was looking for: limited to only binary
permutations, the legal ones are easy to characterize.

what about using multiple coordinates, and then embedding them in a
numeration? It is always possible to encode an n-tuple of natural
numbers as a single one by interleaving the bits.

a legal binary permutation from node A and node B (A < B) can be
written as the tuple (A - 2, s, d) where s denotes the same level
trees and d the dept from it. this is really clumsy and doesnt work..

it looks like what i am looking for is a primitive dup and drop. the
reality is, these are not primitive!



[Reply][About]
[<<][staapl][>>][..]