[Haskell-cafe] Re: All binary strings of a given length
Aleksandar Dimitrov
aleks.dimitrov at googlemail.com
Fri Oct 15 08:41:09 EDT 2010
On Fri, 15 Oct 2010 14:34:42 +0200, rgowka1 <rgowka1 at gmail.com> wrote:
> Amazing, will never find this in any other languagw. But ghci crashes
> for bigger input. Like genbin 20. How to scale this function?
Well, "scaling" this isn't really possible, because of its complexity. It
generates all permutations of a given string with two states for each
position. In regular languages, this is the language {1,0}^n, n being the
length of the string. This means that there are 2^n different strings in
the language. For 20, that's already 1048576 different Strings! Strings
are furthermore not really the best way to encode your output. Numbers
(i.e. bytes) would be much better. You could generate them, and only
translate into strings when needed.
HTH,
Aleks
More information about the Haskell-Cafe
mailing list