Search code examples
probabilityminimize

Algorithm to minimize number of changes in a set of 4 when choosing from a larger set

I have 4 slots on a machine, and I have an order which tells me to put certain items on this machine. There are let’s say 100 items, I have 4 slots, and there are orders which look like this:

4 8 3 3 8 8 8 10 2 7.

I need to be able to fulfill this order with the least amount of slot changes. For example with the input above I should hold the item number 8 on the machine so I don’t have to put it back and pick up another one in it’s place.

The problem is I can not check the next order before it actually reaches me. So it is kind of a guessing game. Anyone has an algorithm that I can look up and apply to this project?

Solution

  • It sounds like you're looking for something like page replacement algorithms. When you reach an order that isn't already on the machine it's a lot like a page miss. You have to evict one of your four cached pages to make room for one you need now.

    There's a lot of options and they all have trade-offs. Generally, the more you know or can reasonably assume about the order stream and the more overhead you can accept, the better your chances of avoiding unnecessary page misses.

    Consider a few questions before choosing:

    1. Within a given stream of orders, what are you willing to assume about the order and frequency of the orders? Assuming a uniform distribution and random order is completely valid.
    2. Do those assumptions tend to be true for most of the order streams you've encountered, or are there several different patterns?
    3. How long do the order streams tend to be?

    If that doesn't help, try implementing a couple like LRU and Clock and testing against actual order streams. To assess their accuracy, you can compare against the theoretical optimum sequence of actions for a particular stream. This algorithm is known as OPT, and only works when you have access to the full stream.