1

Possible Duplicate:
Create Random Number Sequence with No Repeats

I'm trying to generate unique session IDs. Each session ID is a random integer. The main requirement is that each session ID is unique. I'm trying to find the most efficient algorithm to do this.

Scenario: Generate 10 random numbers from 1 to 10 inclusive.

My algorithm:

// Generate unique pseudo-random numbers between 1 and 10 inclusive

vector<int> vList;

for (int i = 1; i <= 10; i++)
{
    vList.push_back(i); 
}

// vList should have {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

for (int j = 1; j <= 10; j++)
{
    int k = (rand() % vList.size());
    cout << vList[k] << " ";
    vList.erase(vList.begin() + k);
}

// Sample output: 5 1 10 7 8 2 4 9 3 6

This algorithm has a time complexity of O(n) and a space complexity of O(n). Is there a more efficient algorithm?

Community
  • 1
  • 1
Siqi Lin
  • 1,237
  • 1
  • 10
  • 25
  • 2
    use a GUID for session ID's... – Mitch Wheat Aug 08 '10 at 16:04
  • Have a look at Fisher-Yates shuffling: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle – Jesper Aug 08 '10 at 16:05
  • @Mitch: A GUID is not random. – andora Sep 02 '10 at 13:07
  • @andora : a GUID is effectively unique. which is what is really required for a session ID – Mitch Wheat Sep 02 '10 at 13:56
  • @Mitch: Ideally a session ID should not be 'just' unique, but unpredictable, else it can be predicted and possibly hijacked/compromised. GUIDs are designed for uniqueness and are potentially predictable and therfore not 'ideal' for session-IDs, but as always, it depends on the application/situation and therefore may be acceptable as session-IDs. A simple hashed GUID+salt may be better. – andora Sep 10 '10 at 19:49
  • @andora: could you describe how a GUID is predictable please. Wouldn't that mean you have a significant amount of information about a client machine? – Mitch Wheat Sep 11 '10 at 00:20
  • @mitch: I understand that sequences of GUIDs are predictable as they are based on local counter values, clock ticks and other 'local' machine factors. This narrows the entropy of GUID sequences significantly to far less than the bit count would suggest and yes, you would need to have access to prior information/GUIDs. I am not saying they are easily predictable, but it should be noted they are designed to be unique and not necessarily random, although they may appear to be. Others, far more competant than I, have suggested so elsewhere. If the app demands it, don't rely on pure GUIDs alone. – andora Sep 11 '10 at 21:42

0 Answers0