Combinations

[spi02]

Hi everyone! My problem basically boils down to this:
I have 71 items, and each item can be either on or off. I need to consider all the combinations (permutations?) and go through a 100 for loop for each of the 2^71 scenarios...on the scale of 10^23. Two questions:

1) My naive implementation is:
for(zero=0;one<2;one++){
    item[0]=zero;
    for(one=0;two<2;two++){
        item[1]=one;
        for(two=0;three<2;three++){
            item[2]=two;
... all the way to
            for(seventy=0;seventy<2;seventy++){
                item[70]=seventy;
                for(market=0;market<100;market++){
                    Computations here;

Is there a better way (faster way) to do this?

2) given the computation part is not too complicated and relatively fast (access several arrays, add stuff together, multiply by some constants) is this feasible to accomplish in a manageable amount of time? (a few hours on my laptop)?

Thanks for your help!

[spi02]

I have since realized that 10^23 is not possible given that the record is 10^12 flops.... I now want to try all permutations with 15 items chosen or less... so it'd be 71C15+71C14+71C13+71C12... scenarios

Does anyone know how I can implement this?

[mahlerfive]

Just 71C15 alone is over 914 trillion combinations. A normal computer can do about 1 billion/sec. This means it will take about 10 days to compute just 71C15.

You might be able to do 71C7 or 71C8 in a reasonable amount of time.

[VernonDozier]

I have since realized that 10^23 is not possible given that the record is 10^12 flops.... I now want to try all permutations with 15 items chosen or less... so it'd be 71C15+71C14+71C13+71C12... scenarios

Does anyone know how I can implement this?

I don't know what calculations you are thinking of, but if you have a 1 gigahertz processor, unless you find a way to simplify it, that's processing 10^9 scenarios per second, and doing 10^23 scenarios is wishful thinking as it would have to be an incredibly simple calculation, and you'd have to spend no time at all on the loop control part of the code, which of course is unrealistic. But even if you can process 10^9 scenarios per second, if you have to do 10^23 of them, that's 10^14 seconds, which is I don't know how many years, but way longer than any of else will be alive.

The other other figure you mentioned (71C15+71C14+71C13+71C12...)
seems more manageable. 71 choose 15 is somewhere in the neighborhood of 10^15. The other terms are going to be significantly smaller, so if we take the whole thing as 10^15 and assume 10^9 scenarios processed per second (extremely wishful thinking, I think), you are looking at one million seconds, or about twelve days, which is longer than you hoped, but you'll still be alive to see the results.

[shaun.husain]

Accessing several arrays is not a simple task as far as processor time is concerned, loads will take a long time, generally speaking you want to try and avoid dereferencing within a loop that will execute many many times. I think each load takes 4 or 5 clock cycles although I've been unable to verify this in the intel architecture manual. Not to mention the extra processor time taken by the JVM to interpret your bytecode into something the processor can understand, plus each loop that is nested creates more and more overhead because each needs to be initialized every time it starts then a comparison needs to happen at the end of each loop to determine if it should jump back to the top and look again. This seems totally infeasible with the process you're currently using. However, if you describe the problem, as far as what the overall program is expected to accomplish someone might be able to help you more.