in reply to Turning very larger numbers into an array of bits

The large number is coming from me. In essence I'm trying to look through every combination of a set that size and find an optimal solution.

I have an array of objects equal to the number of bits and wanted to +1 to try the next combination, evaluate it, and then proceed to the next. Each bit turns that particular element in the corresponding array on/off. I was planning on using bigint to deal with the large numbers.

I considered at first nesting loops but decided I didn't like that approach as with each new element I'd have to keep rolling back over the elements already in the chain to see if it had been used already in the chain, plus I wondered how much CPU I'd burn with the structure.

I also figured with a "bit" approach to the problem, it would probably make it easier to start forking off instances to analyze various combinations.

So at the end of the day here perhaps I'm just making the problem more difficult and I asked the wrong question to begin with.

How would you quickly iterate over every combination of an array with 80 elements where each element is used a maximum of once in the combination? To make it faster, I've already determined the optimal solution will use at least 7 of the elements and no more than 25.

Solutions that precompute the combinations before allowing me to evaluate them don't work well as I have to store all of those combinations and I anticipate only keeping a low number of them - hence I want to evaluate each combination as it comes.

  • Comment on Re: Turning very larger numbers into an array of bits

Replies are listed 'Best First'.
Re^2: Turning very larger numbers into an array of bits
by BrowserUk (Patriarch) on Feb 05, 2017 at 19:03 UTC
    I'm trying to look through every combination of a set that size and find an optimal solution.

    2^80 == 1208925819614629174706176. If you could test 1 million per second, your task will take 38 billion (38,308,547,532) years!

    Even if you only iterate those 80-bit values that have 7 .. 25 bits set, that is still 304202362464000 variations; and would take over 9 years at 1 million per second.

    Update: That is still 636,339,175,131,064,539,743 variations (assuming no ordering requirement) which would take 20,164,371 years at 1 million per second.

    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
      Yes, BrowserUk you are right... we can go from a super duper wildly humongous number to just a super duper humongous number. There is a heck of a lot that I don't understand about the requirements to this OP.

      There is presumably some "test" that will be done on these combinations, which the OP does not mention. Whatever that "test" is, it is bound to take some MIPS and probably a significant number of them!

      Without some more information as to the actual problem that the OP is trying to solve, I do not see any brute force calculation tactics that can do the required math to produce an "optimal solution". I suspect that a better description of the problem could potentially lead to a plausible, "pretty good" rather than an "optimal solution" with many orders less of processing power. Absent that, I am out of ideas.

[reply]
Re^2: Turning very larger numbers into an array of bits
by hippo (Archbishop) on Feb 06, 2017 at 10:37 UTC
    How would you quickly iterate over every combination of an array with 80 elements where each element is used a maximum of once in the combination? To make it faster, I've already determined the optimal solution will use at least 7 of the elements and no more than 25.

    As others have pointed out, that's still an unfeasibly massive number of combinations. Perhaps a considered read through The 10**21 Problem (Part I) (and the subsequent parts) will prove instructive?

[reply]
Re^2: Turning very larger numbers into an array of bits
by Marshall (Canon) on Feb 05, 2017 at 20:50 UTC
    Factorial : There are n! ways of arranging n distinct objects into an ordered sequence.

    With 80 objects,

    n! = 80!
    = 7.156945704 E+118
    =71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000
    There is no program/computer that can do that many tests. This is a humongous number.

    You have absolutely no chance at all without a strategy to reduce the number of tests. A better explanation of what you are testing will probably yield massive orders of magnitude in reduction of computations. Without that, I see ZERO chance.

[reply]
      There are n! ways of arranging n distinct objects into an ordered sequence.

      That would only be true if the OP allowed duplicates; Ie. if a set consisting of 80 x bit 0 was allowed, but the OP does state:

      How would you quickly iterate over every combination of an array with 80 elements where each element is used a maximum of once in the combination?

      Thus the maximium number of sets is 2^80.

      He also made no mention of "ordered".

      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
Re^2: Turning very larger numbers into an array of bits
by Anonymous Monk on Feb 05, 2017 at 20:51 UTC
    It sounds like you're trying to solve an intractable problem like the knapsack problem. This type of algorithm becomes extremely painful around n=30 -- there are over a million possibilities to run through at that point.
[reply]

In Section Seekers of Perl Wisdom