3
$\begingroup$

I am trying to run a loop that cycles through the elements of Tuples[{-1,0,1},116] and terminates when a desired result is found.

Unfortunately, this creates a memory problem due to 116. All of the workarounds that I can find, like IntegerDigits, seem to require positive entries in my tuples.

Is there a good technique to help with this?

$\endgroup$
4
  • 1
    $\begingroup$ You're trying to loop through 22185312344622607535965183080365494317672538611578408721 values? Good luck. $\endgroup$
    – wxffles
    Nov 13, 2014 at 0:07
  • 1
    $\begingroup$ Umm, that's 3^116 tuples. How do you propose to cycle through them? As for using IntegerDigits, one can take the digits base 3 of some number between 0 and 3^116, and subtract 1 from all digits. $\endgroup$ Nov 13, 2014 at 0:09
  • $\begingroup$ I do appreciate how big 3^116 is. For the record, I never had any intention of cycling through ALL of these tuples... just enough for my purposes. $\endgroup$ Nov 13, 2014 at 0:28
  • $\begingroup$ @RossElliot The question indicates ALL, I think. Maybe you should edit it to say "some" or how many. $\endgroup$
    – Michael E2
    Nov 13, 2014 at 0:43

2 Answers 2

2
$\begingroup$

If you need only a few, then randomly choosing them would be easy and perhaps sufficient. The following will produce n = 10 tuples.

With[{n = 10},
 NestWhile[
  DeleteDuplicates @ Join[#, RandomInteger[{-1, 1}, {n - Length[#], 116}]] &,
  {}, 
  Length[#] < n &]
 ]
$\endgroup$
2
$\begingroup$

As others said, there are 3^116 such tuples, so no existing computer will be able to cycle through them in reasonable time. Just to put it in some context, it would take a 1 GHz CPU $3^{116}/10^9/3600/24/365.25 = 7\times 10^{38}$ years to go through this many clock cycles, which is many orders of magnitude longer than the age of the universe.

Recommended reading: http://en.wikipedia.org/wiki/Computational_complexity_theory#Intractability

But putting all that aside, there might be situations when you can't pre-generate all the tuples you need to loop through because you don't have enough memory. So what's a good way to loop though them without keeping all of them in memory? Here's one suggestion:

n = 10; (* 116 is excessive *)
symbols = {-1, 0, 1};

Do[
  (* do something with ... *)
  symbols[[ 1 + IntegerDigits[i, Length[symbols], n] ]]
  ,
  {i, Length[symbols]^n}
]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.