Member Avatar for 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!

  • 4 Contributors
  • 4 Replies
  • 115 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by shaun.husain

Dani AI

Generated

Brief summary and a practical plan based on the existing thread: is trying to enumerate subsets of a 71-element set limited to small subset sizes. Replies from and correctly flagged that brute force across the whole space is impractical, and highlighted important memory/cache and JVM overhead concerns. The useful direction is to stop thinking in terms of deeply nested loops and instead (a) generate only the combinations required, (b) avoid recomputing the inner calculation from scratch, and (c) apply algorithmic pruning or reformulation if the goal is an optimization or search rather than full enumeration.

Generator and incremental state (prototype vs. optimized)

  • Prototype quickly with a generator (Python example below). Good for correctness checks.
  • For speed, use a recursive/backtracking generator that carries an incremental state (running sum, product, etc.) so each include/remove updates that state in O(1). That avoids repeated array traversals inside the hot loop.

Python prototype (good for correctness):

from itertools import combinations

items = [...]       # numeric values
weights = [...]     # per-item constants

for r in range(max_k + 1):
    for combo in combinations(range(len(items)), r):
        score = sum(items[i] * weights[i] for i in combo)
        # process score

Java skeleton with incremental state (better for performance):

void gen(int start, int depth, int maxDepth, int[] sel, double curSum) {
    // process sel[0..depth-1] using curSum
    for (int i = start; i < n; ++i) {
        sel[depth] = i;
        double next = curSum + values[i];
        // handle next
        if (depth+1 < maxDepth) gen(i+1, depth+1, maxDepth, sel, next);
    }
}

Scaling and algorithmic options

  • Use a minimal-change combination generator (revolving-door / Eades–McKay) if the cost can be updated by removing one element and adding another.
  • If the inner calculation is additive, consider meet-in-the-middle: split the set, enumerate small subsets on each half, then combine results via hashing or two-pointer methods.
  • Keep data in primitive arrays, avoid per-iteration allocations, precompute constant multipliers, and implement the hot inner loop in native-compiled code or parallelize across cores if needed.
  • If exhaustive search still cannot finish, switch to heuristics/sampling or reformulate the problem (pruning bounds, branch-and-bound, greedy/metaheuristics).

Recommended workflow: validate correctness with itertools, then reimplement the hot path in an incremental backtracking generator in a compiled language, add pruning or meet-in-the-middle as appropriate, and profile for cache/memory hotspots before further micro-optimizations.

Recommended Answers

All 4 Replies

Member Avatar for 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?

Member Avatar for 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.

Member Avatar for 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.

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.