I have a need to create a list of combinations of numbers. The numbers are quite small so I can use byte
rather than int
. However it requires many nested loops in order to get every possible combination. I'm wondering if there's a more efficient manner to do what I'm after. Code so far is:
var data = new List<byte[]>();
for (byte a = 0; a < 2; a++)
for (byte b = 0; b < 3; b++)
for (byte c = 0; c < 4; c++)
for (byte d = 0; d < 3; d++)
for (byte e = 0; e < 4; e++)
for (byte f = 0; f < 3; f++)
for (byte g = 0; g < 3; g++)
for (byte h = 0; h < 4; h++)
for (byte i = 0; i < 2; i++)
for (byte j = 0; j < 4; j++)
for (byte k = 0; k < 4; k++)
for (byte l = 0; l < 3; l++)
for (byte m = 0; m < 4; m++)
{
data.Add(new [] {a, b, c, d, e, f, g, h, i, j, k, l, m});
}
I was considering using something like a BitArray
but I'm not sure how I could incorporate it.
Any recommendations would be greatly appreciated. Alternatively, perhaps this is the fastest way of doing what I want?
EDIT
Couple of quick points (and apologies I didn't put these in the original post):
- The numbers and the order of them (2, 3, 4, 3, 4, 3, 3 etc) are very important, so using a solution such as Generating Permutations using LINQ won't help because the maximums in each 'column' are different
- I'm not a mathematician, so I apologise if I'm not using the technical terms like 'permutations' and 'combinations' correctly :)
- I do need to populate all of these combinations at once - I can't just grab one or another based on an index
- Using
byte
is faster than using int
, I guarantee it. It's also a lot better on memory usage to have 67m+ arrays of bytes rather than ints
- My ultimate goal here is to look for a faster alternative to nested loops.
- I considered using parallel programming, but due to the iterative nature of what I'm trying to achieve, I couldn't find a way to do it successfully (even with
ConcurrentBag
) - however I'm happy to be proved wrong :)
CONCLUSION
Caramiriel has provided a good micro-optimisation which shaves some time off the loops, so I've marked that answer as correct. Eric also mentioned that it is faster to pre-allocate the List. But, at this stage it seems that the nested loops are in fact the fastest possible way of doing this (depressing, I know!).
If you want to try exactly what I was trying to benchmark with StopWatch
, go with 13 loops counting up to 4 in each loop - that makes about 67m+ lines in the list. On my machine (i5-3320M 2.6GHz) it takes about 2.2s to do the optimised version.
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…