Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Ben Finney <ben+python@benfinney.id.au>
Subject: Re: random.sample with large weighted sample-sets?
Date: Sun, 16 Feb 2014 16:08:27 +1100
References: <20140215224145.68c82eb4@bigbox.christie.dr>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux)
Cancel-Lock: sha1:cyNYCfIyCyd8HFQgcICGrkGWHnA=
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7036.1392527326.18130.python-list@python.org>
Lines: 56
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:66507

Tim Chase <python.list@tim.thechases.com> writes:

> I'm not coming up with the right keywords to find what I'm hunting.
> I'd like to randomly sample a modestly compact list with weighted
> distributions, so I might have
>
>   data = (
>     ("apple", 20),
>     ("orange", 50),
>     ("grape", 30),
>     )

That's not a list, it's a tuple. I think you want a list.

When you want a sequence where each position has a semantic meaning, use
a tuple (such as ‘("apple", 20)’). Each item has a meaning *because of*
the position it's in; if the items were in a different order, they'd
mean different things.

When you want a sequence where the positions don't have a special
meaning – each item means exactly the same no matter if you change the
order – that's sometimes called a “homogeneous” sequence, and you want a
list.

So a “record” should be represented as a tuple, and a “table” of records
should be represented as a list of tuples:

    records = [
            ("apple", 20),
            ("orange", 50),
            ("grape", 30),
            ]

> and I'd like to random.sample() it as if it was a 100-element list.

The implication being, I suppose, that you'd like the number in each
tuple to be a weighting for the probability of choosing that item.

For probability weightings, you should arrange for the weightings to sum
to 1 (instead of 100 in your example). Then each weighting is simply the
desired probability of that item, and those values will work with
various libraries that deal with probability.

> What am I missing? (links to relevant keywords/searches/algorithms
> welcome in lieu of actually answering in-line)

You're looking for a “probability distribution” and “weighted choice”.

Hope that helps!

-- 
 \     “This world in arms is not spending money alone. It is spending |
  `\      the sweat of its laborers, the genius of its scientists, the |
_o__)           hopes of its children.” —Dwight Eisenhower, 1953-04-16 |
Ben Finney