A deck of cards

If not for the order property, you could cram a deck of cards into a 64-bit int. Though if you had a RNG cyclical in full_deck_size, that'd work to preserve the order property. Which would be enough for poker and other stackless or write-only stack card games.

With the cyclical RNG you could pop a card off a full deck in O(1). With incomplete decks (that is, a deck with non-RNG-generated cards removed) you'd need to go through random cards until the generated card is in the deck. The worst-case time-complexity for popping all cards off an incomplete deck would be O(full_deck_size) and the average complexity for popping one card off an incomplete deck would be O(full_deck_size/incomplete_deck_size). Anyhow, incomplete decks would be as fast or slow as full decks, with an extra existence check slowing them down a bit further. The RNG would need a seed with log₂(fac(full_deck_size)) bits, so log₂(52!) = 226 bits for a deck without jokers.

A naive version of the RNG would be to generate a random number between 0 and 52!-1, then convert the number into 52 digits in factorial base. Divide first by 51!, the result is the first card. Divide the remainder by 50!, the result is the second card (note that you have to remove the first card from consideration for the second card index). Continue dividing the remainders until you have 52 cards. Or just generate a shuffled 52 element array of numbers and go through that :P

... I should get back to work now.

Source

#include <inttypes.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef int64_t card_mask;
typedef int8_t card;

typedef struct deck {
  card cards[55];
  int8_t length;
  card_mask mask;
} deck_t;

#define suit_size 13

static const card_mask hearts = suit_size*0;
static const card_mask spades = suit_size*1;
static const card_mask clubs = suit_size*2;
static const card_mask diamonds = suit_size*3;
static const card_mask jokers = suit_size*4;

static const char* suits[5] = {"Hearts", "Spades", "Clubs", "Diamonds", "Jokers"};
static const char* ranks[13] = {
  "Ace", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
  "Jack", "Queen", "King"
};

card_mask remove_cards_from_mask(card_mask deck, card_mask cards)
{
  return deck & ~cards;
}

card_mask add_cards_to_mask(card_mask deck, card_mask cards)
{
  return deck | cards;
}

card_mask query_mask(card_mask deck, card_mask cards)
{
  return deck & cards;
}

card_mask mask_of_card(card c)
{
  return (card_mask)1 << (card_mask)c;
}

card card_for_suit_and_rank(card_mask suit, card_mask rank)
{
  return suit + rank;
}

int deck_initialize(deck_t *deck, int jokers)
{
  card c = 0;
  if (jokers < 0 || jokers > 3) 
    return 0;
  deck->length = 52 + jokers;
  deck->mask = ((card_mask)1 << (card_mask)deck->length)-1;
  for (c=0; c<deck->length; c++) {
    deck->cards[c] = c;
  }
  return 1;
}

void deck_clear(deck_t *deck)
{
  deck->length = 0;
  deck->mask = 0;
}

void deck_shuffle(deck_t *deck)
{
  int8_t i,j;
  card tmp;
  for (i=deck->length-1; i>0; i--) {
    j = rand() % (i+1);
    tmp = deck->cards[j];
    deck->cards[j] = deck->cards[i];
    deck->cards[i] = tmp;
  }
}

card_mask deck_query_mask(deck_t *deck, card_mask m)
{
  return query_mask(deck->mask, m);
}

card_mask deck_query_card(deck_t *deck, card c)
{
  return deck_query_mask(deck, mask_of_card(c));
}

card_mask deck_query_deck(deck_t *deck, deck_t *deck2)
{
  return deck_query_mask(deck, deck2->mask);
}

int deck_add(deck_t *deck, card c)
{
  card_mask m = mask_of_card(c);
  if (query_mask(deck->mask, m)) {
    return 0;
  } else {
    deck->mask = add_cards_to_mask(deck->mask, m);
    deck->cards[deck->length] = c;
    deck->length++;
    return 1;
  }
}

int deck_remove(deck_t *deck, card c)
{
  int8_t i=0, j=0;
  card_mask m = mask_of_card(c);
  if (!query_mask(deck->mask, m)) {
    return 0;
  } else {
    deck->mask = remove_cards_from_mask(deck->mask, m);
    for (i=0,j=0; i<deck->length; i++) {
      if (deck->cards[i] != c) {
        deck->cards[j] = deck->cards[i];
        j++;
      }
    }
    deck->length = j;
    return 1;
  }
}

card deck_pop(deck_t *deck) 
{
  card c;
  if (deck->length < 1) {
    return -1;
  } else {
    deck->length--;
    c = deck->cards[deck->length];
    deck->mask = remove_cards_from_mask(deck->mask, mask_of_card(c));
    return c;
  }
}

const char* suit_string(card s)
{
  if (s >= suit_size*5) 
    return "Invalid";
  return suits[s / suit_size];
}

const char* rank_string(card s)
{
  return ranks[s % suit_size];
}

void print_card(card c)
{
  printf("%s of %s\n", rank_string(c), suit_string(c));
}

void print_deck(deck_t *deck)
{
  int8_t i;
  printf("Deck %p:\n", (void*)deck);
  for (i=0; i<deck->length; i++) {
    print_card(deck->cards[i]);
  }
}

void print_mask(card_mask m)
{
  int i;
  const char* symbols[5] = {"♥", "♠", "♣", "♦", "☻"};
  for (i=0; i<64; i++) {
    if (i%suit_size == 0) printf(" %s", symbols[i/suit_size]);
    if ((m>>i) & 1) putchar('#');
    else putchar('.');
  }
  putchar('\n');
}

int main() 
{
  int i=0;
  deck_t deck, hand;
  card c;
  srand(time(NULL));
  deck_initialize(&deck,2);
  deck_initialize(&hand,0);
  deck_clear(&hand);
  deck_shuffle(&deck);
  printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
  print_mask(deck.mask);
  for (c=0; c<54; c++) {
    if (!deck_query_card(&deck, c)) {
      printf("Error: Deck doesn't have a card.\n");
      print_card(c);
    }
  }
  printf("Hand %p has %d cards and mask %ld.\n", (void*)&hand, hand.length, hand.mask);
  print_mask(hand.mask);
  for (c=0; c<54; c++) {
    if (deck_query_card(&hand, c)) {
      printf("Error: Hand has a card it shouldn't have.\n");
      print_card(c);
    }
  }
  deck_remove(&deck, hearts);
  if (deck_query_card(&hand, hearts)) 
    { printf("Error: Hand has a card it shouldn't have.\n"); print_card(hearts); }
  deck_remove(&deck, spades);
  if (deck_query_card(&hand, spades)) 
    { printf("Error: Hand has a card it shouldn't have.\n"); print_card(spades); }
  deck_remove(&deck, clubs);
  if (deck_query_card(&hand, clubs)) 
    { printf("Error: Hand has a card it shouldn't have.\n"); print_card(clubs); }
  deck_remove(&deck, diamonds);
  if (deck_query_card(&hand, diamonds)) 
    { printf("Error: Hand has a card it shouldn't have.\n"); print_card(diamonds); }
  printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
  print_mask(deck.mask);
  for (i=0; i<5; i++) {
    c = deck_pop(&deck);
    print_card(c);
    deck_add(&hand, c);
  }
  printf("Deck %p has %d cards and mask %ld.\n", (void*)&deck, deck.length, deck.mask);
  print_mask(deck.mask);
  printf("Hand %p has %d cards and mask %ld.\n", (void*)&hand, hand.length, hand.mask);
  print_mask(hand.mask);
  print_deck(&hand);
  if (deck_query_deck(&deck, &hand) || deck_query_deck(&hand, &deck)) {
    printf("Error: Deck and Hand intersect.\n");
  } else {
    printf("Deck and Hand are disjoint.\n");
  }
  for (i=0; i<hand.length; i++) {
    if (deck_query_card(&deck, hand.cards[i])) {
      printf("ERROR ");
    } else {
      printf("OK ");
    }
  }
  printf("\n");
  for (i=0; i<deck.length; i++) {
    if (deck_query_card(&hand, deck.cards[i])) {
      printf("Error: Found a card in Deck that is in Hand.\n");
      print_card(deck.cards[i]);
    }
  }
  print_card(suit_size*5);
  return 0;
}

Output

$ ./a.out 
Deck 0x7fff98907250 has 54 cards and mask 18014398509481983.
 ♥############# ♠############# ♣############# ♦############# ☻##..........
Hand 0x7fff98907210 has 0 cards and mask 0.
 ♥............. ♠............. ♣............. ♦............. ☻............
Deck 0x7fff98907250 has 50 cards and mask 18013848686551038.
 ♥.############ ♠.############ ♣.############ ♦.############ ☻##..........
Eight of Hearts
Seven of Clubs
Ten of Diamonds
Six of Diamonds
Nine of Hearts
Deck 0x7fff98907250 has 45 cards and mask 17714777228828286.
 ♥.######..#### ♠.############ ♣.#####.###### ♦.####.###.### ☻##..........
Hand 0x7fff98907210 has 5 cards and mask 299071457722752.
 ♥.......##.... ♠............. ♣......#...... ♦.....#...#... ☻............
Deck 0x7fff98907210:
Eight of Hearts
Seven of Clubs
Ten of Diamonds
Six of Diamonds
Nine of Hearts
Deck and Hand are disjoint.
OK OK OK OK OK 
Ace of Invalid