[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