Generating All Subsequences Of A Given Length


I am working on a small poker game, and at one point I need to evaluate the hands of all players left. Here’s how the Texas Hold’em (the one I am using) poker style works: at the end of the round you’ll have 5 cards turned on the table, and each player has 2 cards on his own hand. To find the best hand of each player you need to evaluate all the possible combinations of 3 cards on the table plus his 2 cards.

In order to do this I need to find all the subsequences of 3 cards out of 5 total cards. Below you’ll find an algorithm for that. It’s based on the Powerset Algorithm, with a modification that it only prints out when k is equal to the size of the subsequences we want to find. Obviously this could be optimized, as right now it performs unnecessary actions to find all the powerset, but since we are working with small inputs it should be efficient enough.

#include <iostream>

void printSet(int array[],int size){
    int i;

    for (i=1;i<=size;i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;

    return;
}

void findSubsequences (int sub,int n){
    int stack[10],k;

    stack[0]=0; /* 0 is not considered as part of the set */
    k = 0;

    while(1){
        if (stack[k]<n){
            stack[k+1] = stack[k] + 1;
            k++;
        }

        else{
            stack[k-1]++;
            k--;
        }

        if (k==0)
            break;

  if (k==sub)
        printSet(stack,k);
    }

    return;
}

int main(){

    findSubsequences(4,6);

    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *