Need help optimizing this algorithm for extracting combinations from a set

[flalar]

I need help optimizing an algorithm for picking all possible unique combinations of object out of an array. It sort of generating combinatorics but not quite...

public static List<List<Object>> GetCombinations(List<Object> sourceArray)
{
int enumerations;
int numberOfLoops = 0;

List<List<Object>> items = new List<List<Object>>();
int index = 0;
for (enumerations = 1; enumerations <= sourceArray.Count; enumerations++)
{
int i, j;
int sourceListLength = sourceArray.Count;
if (sourceListLength < enumerations)
{
enumerations = sourceListLength;
}
int[] indices = new int[enumerations];
int count = 1;


for (i = 0; i < enumerations;)
{
count *= (sourceListLength - i);
count /= ++i;
}


int indexCap = 1 + sourceListLength - enumerations;

for (i = 0; i < count; ++i)
{
for (j = 0; j < enumerations; ++j)
{
if (items.Count == 0 || items.Count == index)
items.Add(new List<object>());

items[index].Add(sourceArray[j + indices[j]]);
numberOfLoops++;
}
index++;
while (0 < j)
{
indices[--j]++;
if (indices[j] < indexCap)
{
break;
}
}

if (indices[0] < indexCap)
{
for (j = 0; j < enumerations; ++j)
{
if (indices[j] == indexCap)
{
indices[j] = indices[j - 1];
}
}
}
}
}


return items;
}
}

With the input of {"Direct hit", "Indirect hit", "Wound", "Killed"}

The method will output the following sets of objects
{{"Direct hit"},
{"Indirect hit"},
{"Wound"},
{"Killed"},
{"Direct hit", "Indirect hit"},
{"Direct hit", "Wound"},
{"Direct hit", "Killed"},
{"Indirect hit", "Wound"},
{"Indirect hit", "Killed"},
{"Wound" , "Killed"},
{"Direct hit" , "Indirect hit", "Wound"},
{"Direct hit", "Indirect hit", "Killed"},
{"Direct hit" , "Wound" ,"Killed"},
{"Indirect hit","Wound",Killed"},
{"Direct hit","Indirect hit","Wound","Killed"}}


Cheers

[riscutiavlad]

You can do this recursively and using a stack as in backtracking.

In the following code n is the length of the array from which you want to generate combinations and s is the stack. Initialize the first element of the stack with 0 and start on level 1 (p is the level).

void MakeCombinations(int p)
{
for (int i = s[p - 1] + 1; i < n; i++)
// this guaranties that you won't have repeated arrangements of the
// same combination since the first element you put in the stack
// depends on the level you reached on the stack

{
s[p] = i; // put index on stack

HandleCombination(p);
// you must write a method to handle each combination,
// the combination will be the indexes stored in s from 1 to p.

MakeCombinations(p + 1); // call recursively
}
}

void Start()
{
s[0] = -1; // initialize stack
MakeCombinations(1); // start
}