Blocking algorithm for find fixed length permutations

To find all permutations with the leng开发者_如何学编程th of two one could use the follow simple program:

  #include <iostream>
  using namespace std;
  int main(int argc, const char *argv[])
  {
      int l[] = {0, 1, 2, 3, 4, 5};

      const int length = sizeof(l)/sizeof(l[0]);

      for(int i = 0; i + 1 < length; i++)
          for(int j = i + 1; j < length; j++)
              cout << "(" << l[i] << ", " << l[j] << ")" << endl;

      return 0;
  }

But in the application where I need this, the single items are BIG, and needs to be constructed before the set can be used. Therefor I am trying to find algorithm, which does the same but with blocking. The blocking should allow me to have a bank which can be used for caching.

The following illustrates one (manually) created sequence with a bank, which can hold 4 items:

SETS, Cache miss, bank
(0,1) * *         0, 1
(0,2) *           0, 1, 2
(0,3) *           0, 1, 2, 3
(1,2)             0, 1, 2, 3
(1,3)             0, 1, 2, 3
(2,3)             0, 1, 2, 3
(0,4) *           0, 1, 2, 4
(1,4)             0, 1, 2, 4
(2,4)             0, 1, 2, 4
(0,5) *           0, 1, 4, 5
(1,5)             0, 1, 4, 5
(4,5)             0, 1, 4, 5
(2,5)             0, 2, 4, 5
(3,4) *           3, 2, 4, 5
(3,5)             3, 2, 4, 5

Does any of you know a solution to this problem? or can you point in the right direction.

-- Allan

Create a class cache with a method get(int ID), which returns the item with the corresponding ID:

(1) If the corresponding item is already cached, return the cached copy (or a pointer to it)
(2) If it is not: create it, remove an item from the cache, add the new item to the cache, and proceed with (1)

The hard part is to decide which item to remove from the cache in (2). The optimal choice is to remove the item which will not be needed for the longest time. If this is not practical (e.g. because you don't know enough about the access pattern), there are many alternatives.

The most common ones are:

• LRU: remove the least recently used item
• MRU: remove the most recently used item
• LFU: remove the least frequently used item

See the Wikipedia article about cache algorithms for more examples.