random_shuffle не совсем случайный

Сначала вам нужно заполнить генератор псевдослучайных чисел, используя srand.

#include <algorithm>
#include <cstdlib>

...

std::srand(std::time(0));

vector <Card> deck;
//some code to add cards to the deck here
random_shuffle ( deck.begin(), deck.end() );

Примечание по ссылке выше:

Вообще говоря, генератор псевдослучайных чисел должен запускаться только один раз, перед любыми вызовами rand() и запуском программы. Его не следует повторно заполнять или повторно заполнять каждый раз, когда вы хотите сгенерировать новый пакет псевдослучайных чисел.

С текущим С++ (т.е. С++ 11) вы можете использовать алгоритм shuffle, который может принимать объект генератора псевдослучайных чисел (PRNG) (который вы можете посеять) в качестве третьего параметра:

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

int main(int argc, char **argv)
{
  vector<string> v;
  for (int i = 1; i<argc; ++i)
    v.push_back(argv[i]);
  mt19937 g(static_cast<uint32_t>(time(0)));
  shuffle(v.begin(), v.end(), g);
  for (auto &x : v)
    cout << x << ' ';
  cout << '\n';
}

(для GCC 4.8.2 нужно компилировать через g++ -std=c++11 -Wall -g shuffle.cc -o shuffle)

В приведенном выше примере PRNG заполняется текущим системным временем.

Для компиляторов до C++11 у вас есть только алгоритм random_shuffle в STL, но даже с этим вы можете дополнительно указать объект/функцию генератора чисел. Обратите внимание, что вы не можете просто вставить в него объект PRNG, такой как mtl19937 (поскольку он не предоставляет элемент operator()(U upper_bound)).

Таким образом, вы можете поставить свой собственный адаптер следующим образом:

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

struct Gen {
  mt19937 g;
  Gen()
   : g(static_cast<uint32_t>(time(0)))
  {
  }
  size_t operator()(size_t n)
  {
    std::uniform_int_distribution<size_t> d(0, n ? n-1 : 0);
    return d(g);
  }
};

int main(int argc, char **argv)
{
  vector<string> v;
  for (int i = 1; i<argc; ++i)
    v.push_back(argv[i]);
  random_shuffle(v.begin(), v.end(), Gen());
  for (vector<string>::const_iterator i = v.begin(); i != v.end(); ++i)
    cout << *i << ' ';
  cout << '\n';
}

Поместите строку:

srand (time (0));

в вашем коде, прежде чем вы сделаете что-нибудь еще, например, в начале main().

Без этого всегда будет использоваться семя по умолчанию 1, что приведет к идентичным последовательностям из rand() и всего, что его использует.