[<<][compsci][>>][..]

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

Problem solved.

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
next post.


-- 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  <-> [2]
--  OIIII  <-> [0]
--  IIIIO  <-> [4]
--
-- 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

[Reply][About]

[<<][compsci][>>][..]