On 09/16/2012 12:05 AM, Dave Angel wrote:
> On 09/15/2012 11:48 PM, aklei...@sonic.net wrote:
>>> On 09/15/2012 10:03 PM, Scurvy Scott wrote:
>>>>> That list would fill all the PC's on the planet a few billions times.
>>>>> The number of items in the list has 25 digits in it. print 32**16
>>>>>
>>> I can't see any reason why it changes anything. The world doesn't have
>>> enough disk space to store *every* address. If you need to calculate
>>> all of them, you don't have enough time.
>>>
>>> You need to rethink whatever your real problem is. For example, if you
>>> were really trying to crack a safe with 32 numbers on the dial and 16
>>> settings to open it, perhaps you should forget all of it and get some
>>> nitro. Or a stethoscope. Or bribe somebody who knows the combination.
>>> If you have to try all of the combinations systematically, you'll never
>>> get there.
>> We can probably all agree that there aren't enough resources (time,
>> memory, etc) to solve the problem, but that doesn't make the problem
>> uninteresting.
>> What interests me, and I acknowledge that this is more a question for a
>> computer science forum than a python one, is: can this be done in a non
>> recursive way so the limiting factor will be time, not memory? I couldn't
>> think of a way.
>>
> it can certainly be done non-recursively, as I showed with a relatively
> simple list comprehension, borrowing the idea from Peter Otten.
>
> import itertools
> chars = "ab5"
> result = ["".join(item) for item in itertools.product(*[chars]*4)]
>
> Non-recursive doesn't mean "uses little memory," however.
>
> Since the problem is to build a list, it will use lots of memory. If
> the problem were instead to make a generator that yields all possible
> strings,
>
> import itertools
> chars = "ab5"
> result_generator = ("".join(item) for item in itertools. product(*[chars]*4))
>
> Now, you could write a loop that examined all these items (pretending
> you had unlimited time), something like:
>
> for item in result_generator:
> if test_safe(item):
> print item, "cracked the algorithm"
>
> obviously, you'd need a longer chars, and to change *4 to *16, if you
> actually wanted to do the original dataset.
>
> And if you don't want to use itertools, you can trivially do it in a
> loop, since you're basically just counting, base 32.
>
A slight addendum. The other, recursive, implementation ran out of
memory not because of recursion, but because it was building a ginormous
list. The recursion is limited to 16 levels, as written.
So that algorithm could also be turned into a generator, if we wanted to
be time-limited and not memory limited.
--
DaveA
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
