1

I'm trying to figure out the best way of doing the following:
I have a list of values: L
I'd like to pick a subset of this list, of size N, and get a different subset (if the list has enough members) every X minutes.
I'd like the values to be picked sequentially, or randomly, as long as all the values get used.

For example, I have a list: [google.com, yahoo.com, gmail.com]
I'd like to pick X (2 for this example) values and rotate those values every Y(60 for now) minutes:

minute 0-59: [google.com, yahoo.com]
minute 60-119: [gmail.com, google.com
minute 120-179: [google.com, yahoo.com]
etc.

Random picking is also fine, i.e:
minute 0-59: [google.com, gmail.com]
minute 60-119: [yahoo.com, google.com]

Note: The time epoch should be 0 when the user sets the rotation up, i.e, the 0 point can be at any point in time. Finally: I'd prefer not to store a set of "used" values or anything like that, if possible. i.e, I'd like this to be as simple as possible.

Random picking is actually preferred to sequential, but either is fine. What's the best way to go about this? Python/Pseudo-code or C/C++ is fine.

Thank you!

Sjint Skovast
  • 21
  • 4

1 Answers1

1

You can use the itertools standard module to help:

import itertools
import random
import time

a = ["google.com", "yahoo.com", "gmail.com"]
combs = list(itertools.combinations(a, 2))
random.shuffle(combs)
for c in combs:
    print(c)
    time.sleep(3600)

EDIT: Based on your clarification in the comments, the following suggestion might help.

What you're looking for is a maximal-length sequence of integers within the range [0, N). You can generate this in Python using something like:

def modseq(n, p):
    r = 0
    for i in range(n):
        r = (r + p) % n
        yield r

Given an integer n and a prime number p (which is not a factor of n, making p greater than n guarantees this), you will get a sequence of all the integers from 0 to n-1:

>>> list(modseq(10, 13))
[3, 6, 9, 2, 5, 8, 1, 4, 7, 0]

From there, you can filter this list to include only the integers that contain the desired number of 1 bits set (see Best algorithm to count the number of set bits in a 32-bit integer? for suggestions). Then choose the elements from your set based on which bits are set to 1. In your case, you would use pass n as 2N if N is the number of elements in your set.

This sequence is deterministic given a time T (from which you can find the position in the sequence), a number N of elements, and a prime P.

Community
  • 1
  • 1
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
  • The values are accessed from multiple different languages, so this wouldn't work unless I stored the combination results themselves and rotated those every X seconds, which isn't the simplest solution.. – Sjint Skovast Jul 18 '11 at 00:17
  • 1
    Sorry, I don't understand what you mean by "accessed from multiple different languages". Do you mean *programming* languages or *spoken* languages? What does "accessed" mean? – Greg Hewgill Jul 18 '11 at 00:18
  • I mean programming languages. i.e: L is available in the DB, and is read in by a program in C++, and one in Python. I'd like them both to return the same subset, given the same rotatation time, epoch and subset size. I'm currently planning on just using a modulo operation, but, was hoping SO would have something better. – Sjint Skovast Jul 18 '11 at 00:22
  • @Sjint, would using a stored procedure be the best option then? What DB are you using? – svick Jul 18 '11 at 00:43
  • @Greg: While I think your solution is workable, I don't think it's simple, or elegant (although, of course, that is only my opinion). Please check my edit in the question to see my current solution which seems to be far simpler. – Sjint Skovast Jul 18 '11 at 00:51
  • Well, your proposed solution (a) doesn't describe how to generate `vallist` (I'm assuming that `l` inside the function should be `vallist`), (b) always appears to select adjacent members from `vallist`, (c) doesn't address the "random" requirement that you suggested. You can certainly come up with a simpler answer to a different question. – Greg Hewgill Jul 18 '11 at 00:58
  • @Greg: Random selection was preferable, but not required, as per my original question. Is what you suggested the only way you can think of to get random selection? – Sjint Skovast Jul 18 '11 at 01:03
  • No, but it's one way and it's reasonably straightforward. If you don't like it, you don't have to use it. – Greg Hewgill Jul 18 '11 at 01:05
  • I also apologize for posting incorrect code initially (using l, which was in my global scope). I've updated my question. If there's nothing new, I'll go ahead and accept your answer, as you're right, it satisfies the "preferably" random bit, which mine does not. – Sjint Skovast Jul 18 '11 at 01:08