[Haskell-cafe] Re: All binary strings of a given length

[Eugene Kirpichov]

Actually my ghci doesn't crash for genbin 25 (haven't tried further),
though it eats quite a bit of memory.
How are you going to use these bit strings? Do you need all of them at once?

2010/10/15 Aleksandar Dimitrov <aleks.dimitrov at googlemail.com>:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>



-- 
Eugene Kirpichov
Senior Software Engineer,
Grid Dynamics http://www.griddynamics.com/