# Algorithm for randomly choosing learning cards

I'm programming a learning software. It works with question-/answercards. I´m searching for a algorithm that gives me a higher probability for cards that the user has answered wrong.

My actual idea (edit: Inverse transform sampling) is that each card has an integer which indicates how often the user has answerd the question wrong. Count all integer-values, creating a random integer between 0 and the counted integer-values and use this integer to go through my cards and count their integers until I reached the random integer. Then I reach the integer I choose this card :-)

But there must be a better solution ;-)

Edit: Rejection Sampling

N = number of cards
M = score of the highest card
c = random (1 - N)
x = random (1 - M)

if (x <= (score of card-nr: c)) accept card!
else create new c & x and goto if-querry


That means that cards with a higher score will choosen more often.

• By the way, what you are doing is essentially inverse transform sampling.
– user856
Commented Mar 23, 2011 at 22:14
• @Rahul Narain: good to know, thx Commented Mar 24, 2011 at 15:41

You solution seems ok if you don't mind sorting the cards each time. Here is a different method: choose a card at random and a number at random from 0 to the max card score. Accept the chosen card if the number is at most the card score. Otherwise, repeat. This method is rejection sampling on the graph of card scores.

• The algorithm in the question requires no sorting.
– user856
Commented Mar 23, 2011 at 22:15
• It does require a linear traverse through the list of cards; this method is also prone to this behavior if there are a few cards with much higher score than the others. Commented Mar 24, 2011 at 5:28
• I have looked at the artical but don´t understand it :-( Can you try to explain the algorithm to me? Commented Mar 24, 2011 at 14:01
• @myName: I did it in the answer. I'll try again: If there are $N$ cards, choose a random number $c$ between $1$ and $N$. Now choose a random number $x$ between $1$ and $M$, where $M$ is the max score of all cards. If $x \le \mbox{score}(c)$ then accept card $c$. Otherwise, start again. If you think about the score graph, you're choosing a point $(c,x)$ that lies below the graph.
– lhf
Commented Mar 24, 2011 at 14:29
• I think i have anderstood you :-) Can you please have a look at the example above and confirm or correct it. Commented Mar 24, 2011 at 15:21

Here's a more efficient algorithm, requiring some space. You keep a lookup table containing the card to pick for each value of your random integer. The table is init by letting cell $i$ point at card $i$. When you increase the prominence of card $j$, just add a new cell pointing to $j$.

If you are memory-savvy, then you can use the following algorithm. Put all your cards in a balanced binary tree. Each card maintains both its own prominence and the sum of prominence of it and all its descendants. To select a card, use binary search. When you increase the prominence of a card, you need to update only its ancestors. So both operations take logarithmic time.

No, that's pretty much the best way of producing that distribution. You might want to add something that slowly decreases the weight of correctly-answered flashcards or your total counts just keep inflating, which becomes a problem after a while.

• i thought i multiply the score with 0,X if the answer was right and with 1,X if the answer was wrong ;-) Commented Mar 23, 2011 at 22:37
• You're right that for that application, the slow running time doesn't matter. In some applications it might, and then you can be smarter and use a more efficient algorithm. Commented Mar 24, 2011 at 5:26

You probably don't want to make the initial numbers 0, or you'll never see a new card once you've had a wrong answer to something else.