Mon Mar 26 15:55:16 CEST 2012
Indexing binomial combinations
What is the simplest way to "name" the different combinations in a
select I from N problem?
I.e. select 2 from 3:
1 -> .||
2 -> |.|
3 -> ||.
Select 2 from 4:
1 -> ..||
2 -> .|.|
3 -> .||.
4 -> |..|
5 -> |.|.
6 -> ||..
What I used above is just binary counting (digit reversed) and
skipping all entries that don't have the proper number of elements.
This seems quite straightforward, but I prefer something that doesn't
need a search. For my app I is usually a lot less than N (mostly 1
and in some cases 2), how do I get the sequence number in the list
above starting from the coordinates of the empty spots? For I=1 this
is already the desired encoding:
1 -> .||| |
2 -> |.|| |
n -> |||| .
Actually it's quite trivial when using a nested datastructure:
- N lists, first element from N
- N-1 lists, second element, each from N-1 possibilities
EDIT: Sun Apr 1 12:02:11 CEST 2012
I made it work with the code below. Question is if this is really
useful, and if an implicit table ref isn't a better way to go because:
* final result needs to be a table
* a single function acting on a table might be simpler to use than a
bunch of functons + shuffler routines.
EDIT: Actually this is not even correct. It indexes proper
permutations while what I need is just selections (all permutations of
outputs and inputs separately can use the same function)
I'm moving to an implicit, imperative array-based implementation. See
-- A multi-directional equation node is represented by a tree of
-- functions, one for each possible combination if inputs and outputs.
-- Each level in the tree fixes one output. Canonical ordering of
-- outputs is from left to right starting at index 0, and spanning all
-- remaining nodes at a particular level (i.e. first level has N
-- elements, second level N-1, ...)
-- I.e. for a 5 node, 1 output network
-- IIOII <-> 
-- OIIII <-> 
-- IIIIO <-> 
-- for a 5 node, 2 output network:
-- IIOOO <-> [0,0]
-- OOOII <-> [4,3]
-- IOOOI <-> [0,3]
-- The ordering of the EquFun list follows a canonical list of
-- permutations (defined elsewhere). See equFunIndex
data EquImpl = EquImplFun EquFun
| EquImplSelect [EquImpl]
equImplRef' :: EquImpl -> [Int] -> EquFun
equImplRef' = f where
f (EquImplFun fn)  = fn
f (EquImplSelect fns) (i:is) = f (fns !! i) is
-- Convert list of I/O to permutation tree index.
data EquIO = EquIn | EquOut deriving (Eq, Show)
equIO2Ref = f  0 where
f c n  = c
f c n (EquOut:e) = f (c ++ [n]) n e
f c n (EquIn:e) = f c (n+1) e
-- For debugging: using 0,1, instead of EquOut/EquIn
equIO = map f where
f 0 = EquOut
f 1 = EquIn