Selecting 10 items based on N number types

Question

I am writing a program that has to select 10 items randomly from a database . the criteria is that its type should be based on users choice .

So if the user chooses type 1 the program has to choose 10 items of type 1

if the user chooses type 1 and 2 the program has to choose 5 items from type 1 and 5 items from type 2

if the user chooses type 1 , 2 and 4 the program has to choose 3 items for each type and one of the types must have and extra item to get 10 items and which type gets an extra question has to be random.

So This has to be done for N number of types that the user can choose from .

Any suggestions on the way this can be achieved ?

By the way I am trying to build a Random generator so the result has to be random each time.

Ps: I am coding in python , but any language code is fine .

PS: I am already able to select items using SQL WHERE Clause , That is not the real problem.

the problem is once I have gotten items of each of the selected types , I have to select exactly 10 items with the above proportions , (i.e) : if 4 types are chosen 2 items for each type and and exactly 2 extra items in any two of the types .

What have you got so far? Stack Overflow is a good place to hints and idea for `homework` and this type of questions at large, _provided_ that you show that you have tried to solve the problem yourself... — mjv, Oct 25 '11 at 04:17
@mjv : I tried solving it using if statements , As you could have guessed it wasn't very pretty , By the way this is not exactly home work — Gautam, Oct 25 '11 at 04:32
@BrendanLong Ya I am using at the moment sqlite , but I will be switching to mysql or Posgresql — Gautam, Oct 25 '11 at 04:33
@BrendanLong : Its a personal project that i building at home. So not exactly home work. — Gautam, Oct 25 '11 at 04:39

Raymond Hettinger · Answer 1 · 2011-10-25T04:47:16.900

One way is to scan the DB in a single pass, building up your ten selecions. Here's some pseudo code:

Query the whole database for records meeting the user's criteria
Build-up the first ten encountered in a results list
If any additional records arise, decide randomly whether to include it (the n-th item should be included with a probability of P(10/n)): if random() < 10.0 / n: ...
If it it is to be included, randomly choose a previous selection to swap out: i = randrange(10)

In Python:

result = []
for n, row in enumerate(cursor.execute(user_query), 1):
    if n <= 10:
        result.append(row)
    elif random() < 10.0 / n:
        i = randrange(10)
        result[i] = row

Alternatively, if the database non-queryable, is huge, and has a high percentage of records expected to match the user criteria, you could randomly select records from the entire DB until you've found ten unique records that match the criteria:

result = set()
while len(result) < 10:
     record = random.choice(entire_db)
     if record not in result and matches(record, user_criteria):
          result.add(record)

The latter algorithm is one of the two used by Python's own random.sample() function.

If you can run queries though and the number of matching records can fit in memory, the whole thing boils down to:

random.sample(list(cursor.execute(user_query)), 10)

You lost me at "loop over the whole database". That sounds incredibly inefficient. — Brendan Long, Oct 25 '11 at 04:24
The first two steps amount to: SELECT * FROM some_table WHERE some_user_criteria. You have to identify you population somehow. — Raymond Hettinger, Oct 25 '11 at 04:27

score 1 · Answer 2 · edited May 23 '17 at 12:27

Basically you need to get it into this form:

SELECT item
FROM items
WHERE type = ...
ORDER BY RANDOM()
LIMIT 10

See Select random from an SQLite table. This should work for PostgreSQL too.

This well let the database do most of the work for you, and all you need to do is figure out how to pass your types in as arguments, which is dependent on your database library.

For multiple, I'd probably just run several queries or dynamically generate one with multiple unions.

You can do that like this:

SELECT item
FROM items
WHERE type = type1
ORDER BY RANDOM()
LIMIT 5
UNION ALL
SELECT item
FROM items
WHERE type = type2
ORDER BY RANDOM()
LIMIT 5

Which can be generated by Python like this:

types = ("type1", "type2", "type3")
limit = 10 // len(types) # be careful, for 11 or more types, this will set the limit to 0
sql = """
    SELECT item
    FROM items
    WHERE type = ?
    ORDER BY RANDOM()
    LIMIT %s
""" % (limit)
unioned_sql = " UNION ALL ".join([sql for i in range(len(types))])
result = cursor.execute(unioned_sql, types)

The syntax might be wrong -- I haven't used the DB API in a while. It should give the idea though.

You mentioned that a problem is that you need to select exactly 10 items, including extras if the proportion doesn't work out to exactly 10, so maybe it would be better to hard-code the limit at 10 (select up to 100 items), and then trim the list after getting it from the DB.

score 0 · Answer 3 · answered Oct 25 '11 at 04:42

Some things you might find useful:

Python

random.choice(seq)

Return a random element from the non-empty sequence seq.

random.sample(population, k)

Return a k length list of unique elements chosen from the population
sequence. Used for random sampling without replacement.

Usage:

>>> import random
>>> random.choice([1, 2, 3, 4, 5])  # Choose a random element
3
>>> random.sample([1, 2, 3, 4, 5],  3)  # Choose 3 elements
[4, 1, 5]

SQL

SQL WHERE Clause

The WHERE clause is used to extract only those records that fulfill a specified criterion.

Usage:

SELECT * FROM Items
WHERE Type=1

Selecting 10 items based on N number types

3 Answers3

Some things you might find useful:

Python

SQL