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

[Daniel Gorín]

I expect this one to run in constant space:

import Data.Bits

genbin :: Int -> [String]
genbin n = map (showFixed n) [0..2^n-1::Int]
    where showFixed n i = map (bool '1' '0' . testBit i) [n-1,n-2..0]
          bool t f b = if b then t else f

Daniel

On Oct 15, 2010, at 9:43 AM, Eugene Kirpichov wrote:

> 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/
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe