[Caml-list] Holding a set of random integers of very wide range?

[john.chu@east.sun.com]

Diego Olivier Fernandez Pons writes:
> If you give me some more informations (on typical ranges that you can
> find in unicode subsets) I will be able to give more precise answers

This brings up a possibly related question that I have.

For reasons I tried to explain in a previous draft of this e-mail and
has been cut due to the amount of space it took, I need to generate
multiple permuted lists of integers ranging from 0 to approximately
2^100 (or more, it's a bit open-ended unfortunately).

Since I only need one value at a time, I can use a lazy list for
this. i.e., the head holds a value and the tail is a suspension of the
state I need to generate the next value.  No big deal there.

The big deal, for me anyways, is that the state I need is tracking the
integers that I've already used (so that I don't generate the same one
twice) given that the range of possible values is so large.

I'm currently using the very low-tech solution of maintaining a list
of ranges of used values.  (i.e., when I use a value that would link 2
different ranges, I go coalesce the list.  The worst case would be if
I picked all the odd integers or all the even integers.)

Given the recent talk of Patricia trees and bit sets, I was wondering
if some variant of either one of those, or some other representation
would be better for what I'm doing?  (I figure at the very least I
ought to be using a tree of ranges of used values.  I'm currently
using the Big_int module to represent my integers.)

BTW, it's extremely unlikely I will ever need every single value in
the lazy list.  I will probably have queried the garbage collector and
declared defeat long before then.  I'm hoping that, at worst, I will
need only several thousand values from each permuted list.  But I
don't want to precompute them since I may not need several thousand
values from some lists and others might need more.  So I want to
generate only the numbers that are necessary.  (Sorry, this bit only
makes sense if you knew what I'm using this for.  The short
description would be backtracking to find a set of variable values
which satisfy a bunch of contraints where there can be multiple
possible solutions of which I want a random one where variable values
can be mapped onto a potentially very large range of integers.  I'm
applying as many constraints before backtracking as possible to reduce
the state space to search.)

Thanks.

					john
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners