You know what has bothered me all day?
Generating non-contiguous subsets from an n-length array.
You know what is sad about that fact?
It wasn't my problem to solve, it was somebody else's. But the quest to solve it nagged me, and I've spent mental hours dwelling upon it. I avoided it, because it wasn't my problem, still thought about. Arrived at the conclusion that it would probably require recursion to accomplish it, left it at that. Came back and said "well, it it is going to require recursion, what would be the proper recursive function to do it?" And, of course, I wrote one. But it was inefficient, required an extra object just to monitor the situation because although I arrived at all possible subsets, I would have included a lot of duplicates without the extra object I was using to monitor things. And then
that bugged me. So I came back to it, started over from scratch, dumped the recursion and finally arrived at a winning function, which I then turned into a generic.
static List<T[]> CreateSubsets<T>(T[] originalArray)
{
List<T[]> subsets = new List<T[]>();
for (int i = 0; i < originalArray.Length; i++)
{
int subsetCount = subsets.Count;
subsets.Add(new T[] { originalArray[i] });
for (int j = 0; j < subsetCount; j++)
{
T[] newSubset = new T[subsets[j].Length + 1];
subsets[j].CopyTo(newSubset, 0);
newSubset[newSubset.Length - 1] = originalArray[i];
subsets.Add(newSubset);
}
}
return subsets;
}
And now it's grating on my nerves that it took me so long to arrive at something so simple.
And you know
why I've spent the better part of the day dwelling on this? Because some dude somewhere posted a homework problem yesterday on the web that said he had to find all zero-sum subsets within a 5 integer array. Which, of course, I solved in relatively short order, but I had limited it to contiguous subsets. I didn't post the answer, merely a suggestion, because (after all) it was homework and dude should figure it out for himself. But then he came back and said he couldn't figure out my suggestion but also indicated via his additional description that it might not only have to find subset a-b-c but also a-c-e!
