Re: encoding a vector
- From: Harri Haanpaa <harhaa@xxxxxxxxx>
- Date: Mon, 28 Jan 2008 18:47:19 +0200 (EET)
On 2008-01-28, muede73 <muede73@xxxxxx> wrote:
Hi,
i need to encode a integer vector as some integer.
v := [ a_1,...,a_n ] , a_i \in {0,n-1}
There is a condition v holds :
a_1+...+a_n <= n^2/4 (1)
I could do it with a base-n-code, but I am looking
for something more efficient, maybe by exploiting (1).
By efficient I mean, that it should fit in a 64bit word for n <= ~20.
A constraint is, that it has to be incremental updateable.
You should specify more clearly what you mean by incrementally updateable.
Anyway, for n=20, the sum is <= 100, so you can think of the problem
so that you have 100 balls to place in 21 numbered urns (one of
which could be a_0).
If you have b balls to place in u urns, the number of combinations
is {b+u-1 \choose u-1} so here you would have {120 \choose 20}
combinations. You could find ranking and unranking algorithms for
k-subsets of a finite set to map (bijectively) each combination to
an integer. These would not be very easily incrementally updatable,
but they would be a compact representation at least.
Harri H.
.
- References:
- encoding a vector
- From: muede73
- encoding a vector
- Prev by Date: Re: Huge database
- Next by Date: Re: Simulation: digital vs analogue
- Previous by thread: encoding a vector
- Next by thread: LTL vs. CTL
- Index(es):
Relevant Pages
|
