All possible combinations of n items selected randomly from a set of x items (algorithm)

Question

I have a set of x string items e.g("A","B","C","D","E","F") I need to know the formula that calculates how many combinations of n items and what is the algorithm that generates all possible combinations e.g if we need to select 4 items from the list randomly. those 4 items could be: ("A","B","C","D") or ("A","B","C","E") or ("A","B","C","F") or ("A","B","D","E") ...etc I need the formula that calculates how many sets of items will be generated without repetition, that is we consider ("A","B","C","D") as one of the resulted combinations we cannot consider the same items as another resultant combination with replacing the positions of the items in the set like ("A","B","D","C") Also I need the algorithm that generates all possible combinations in any programming language. [C#,VB.NET,Java,C++]

Thank you for any help.

Answer 1

Choosing p out of n items, this is the formula to tell you how many combinations there are.

                  n!
n choose p  = -----------
               p! (n-p)!

Google calculator will do the math for you:

http://www.google.com/search?q=6+choose+4

6 choose 4 = 15

Answer 2

You need the Binomial Theorem, and you need nested loops. As for an implementation in one of your programming languages, not too difficult to write. If you look around you will find that this question is regularly asked on SO, and you will find people voting to close your question for that reason.

Answer 3

You can also go for Lexicographic ordering.

Something like this:

#include <stdio.h>

void print(const int *v, const int size)
{
    int i;
    if (v != 0) {
        for (i = 0; i < size; i++) {
            printf("%4d", v[i] );
        }
        printf("\n");
    }
} // print


void visit(int *Value, int N, int k)
{
    int i;
    static level = -1;
    level = level+1; Value[k] = level;

    if (level == N)
        print(Value, N);
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0)
                visit(Value, N, i);

    level = level-1; Value[k] = 0;
}


main()
{
    const int N = 4;
    int Value[N];
    int i;
    for (i = 0; i < N; i++) {
        Value[i] = 0;
    }
    visit(Value, N, 0);
}

Answer 4

You can compute the number of combinations using Pascal's triangle. To find the actual combinations you can use plain recursion.

Answer 5

Here's my tested solution (the last method show an example of usage in form of unit test):

/// <summary>
/// Returns the number of combinations with no repetition of n element taken s at time, with n = numOfElements
/// and s = setSize
/// </summary>
/// <param name="numOfElements"></param>
/// <param name="setSize"></param>
/// <returns></returns>
public static long GetNumberOfCombinationsWithNoRepetition(int numOfElements, int setSize)
{
        long val = 1;
        for (int i = 0; i < setSize; i++)
        {
                val *= numOfElements - i;
        }
        return val;
}

/// <summary>
/// Returns the k-th combination (without repetitions) on an array of n objects
/// taken s at time, with s = sizeOfSet.
/// N.B. k must be greater or equal than zero, and lower than the number of combination.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="k"></param>
/// <param name="objs"></param>
/// <param name="sizeOfSet"></param>
/// <returns></returns>
public static T[] GenerateKthCombination<T>(long k, T[] objs, int sizeOfSet)
{
        int n = objs.Length;
        int[] possibilitiesInsideGrp = new int[sizeOfSet];
        int[] grpSize = new int[sizeOfSet];
        possibilitiesInsideGrp[0] = n - sizeOfSet + 1;
        grpSize[0] = 1;
        for (int i = 1; i < sizeOfSet; i++)
        {
                possibilitiesInsideGrp[i] = n - sizeOfSet + i + 1;
                grpSize[i] = grpSize[i - 1] * possibilitiesInsideGrp[i - 1];
        }
        T[] combObjs = new T[sizeOfSet];
        List<int> avail = new List<int>(objs.Length);
        for (int i = 0; i < objs.Length; i++)
                avail.Add(i);

        long remainder = k;
        for (int i = 0; i < sizeOfSet; i++)
        {
                int index = (int)(remainder / grpSize[sizeOfSet - i - 1]);
                remainder = remainder % grpSize[sizeOfSet - i - 1];
                combObjs[i] = objs[avail[index]];
                avail.RemoveAt(index);
        }
        return combObjs;
}


[Test]
public void TestGenerateKthCombination()
{
        char[] chars = new char[] { 'A', 'B', 'C', 'D' };
        List<string> enumerations = new List<string>();

        var num = Utilities.GetNumberOfCombinationsWithNoRepetition(chars.Length, 3);

        for (int i = 0; i < num; i++)
        {
                var comb = Utilities.GenerateKthCombination<char>(i, chars, 3);
                enumerations.Add(new string(comb));
        }

        Assert.IsTrue(enumerations[00] == "ABC");
        Assert.IsTrue(enumerations[01] == "ABD");
        Assert.IsTrue(enumerations[02] == "ACB");
        Assert.IsTrue(enumerations[03] == "ACD");
        Assert.IsTrue(enumerations[04] == "ADB");
        Assert.IsTrue(enumerations[05] == "ADC");
        Assert.IsTrue(enumerations[06] == "BAC");
        Assert.IsTrue(enumerations[07] == "BAD");
        Assert.IsTrue(enumerations[08] == "BCA");
        Assert.IsTrue(enumerations[09] == "BCD");
        Assert.IsTrue(enumerations[10] == "BDA");
        Assert.IsTrue(enumerations[11] == "BDC");
        Assert.IsTrue(enumerations[12] == "CAB");
        Assert.IsTrue(enumerations[13] == "CAD");
        Assert.IsTrue(enumerations[14] == "CBA");
        Assert.IsTrue(enumerations[15] == "CBD");
        Assert.IsTrue(enumerations[16] == "CDA");
        Assert.IsTrue(enumerations[17] == "CDB");
        Assert.IsTrue(enumerations[18] == "DAB");
        Assert.IsTrue(enumerations[19] == "DAC");
        Assert.IsTrue(enumerations[20] == "DBA");
        Assert.IsTrue(enumerations[21] == "DBC");
        Assert.IsTrue(enumerations[22] == "DCA");
        Assert.IsTrue(enumerations[23] == "DCB");
}

EDIT: sorry i miss the part "(...)we cannot consider the same items as another resultant combination with replacing the positions of the items in the set like(...)"

In my solution, the order IS important

Answer 6

The formula for a combination, which is what you describe, is given in @Mark Harrison's answer. However, plug in this equation and it will explode, because the mathematics are intended to cancel out.

For example, 50 choose 49 -- this is the same as choosing which element to exclude, so there are 50 choices. However, the formula would require you to compute

   50!       3.04140932e64
-------- = ----------------- = 50
1! * 49!   1 * 6.08281864e62

The equation you "really" want for x choose y is

x * (x-1) * ... * (x-n+1)
-------------------------
n * (n-1) * ... * 2 * 1

Some easy C code [note that this optimizes that C(x,y) = C(x,x-y) -- this should be easy to see from the combination formula]:

int c(int x, int y)
{
    int num = 1, denom = 1;
    int i;
    if (y > x-y)
        y = x - y;
    for (i = 0; i < y; ++i)
    {
        num *= (x - i);
        denom *= (y - i);
    }
    return num/denom;
}

So, if you want all possible combinations of letters "ABCDEF" where you pick 4 letters, that is c(6,4).

Answer 7

I need the algorithm that generates all possible combinations in any programming language.

Okay, here is a one-line solution in Haskell:

import Data.List (subsequences)

n `outOf` xs = filter ((n ==) . length) (subsequences xs)

test = 4 `outOf` ["A", "B", "C", "D", "E", "F"]

*Main> test
[["A","B","C","D"],["A","B","C","E"],["A","B","D","E"],["A","C","D","E"],["B","C
","D","E"],["A","B","C","F"],["A","B","D","F"],["A","C","D","F"],["B","C","D","F
"],["A","B","E","F"],["A","C","E","F"],["B","C","E","F"],["A","D","E","F"],["B",
"D","E","F"],["C","D","E","F"]]
*Main> length test
15

Answer 8

Yeah, Pascal's triangle works.

int dp[MAX_X][MAX_Y] = {0};

dp[0][0] = 1;
for (int i = 1; i <= X; i++) {
    dp[i][0] = dp[i][i] = 0;
    for (int j = 1; j < min(i, Y + 1); j++)
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}

print(dp[X][Y])

Alternatively, you might do something using the sliding-window trick.

Then again, I think that the formula works better, unless the values get to be too big.