generate binary one bit change between all members

ı have a question. ı want to generate binary list .but between members of the list will be only one bit change.

oneBitAll :: Integral a => a -> [[String]]

for n=2

Output:

["00","01","11","10"] ve ["00","10","11","01"]

n=3

oneBitAll 3
[["000","001","011","010","110","111","101","100"], ["000","001","011","111","101","100","110","010"], ["000","001","101","100","110","111","011","010"], ["000","001","101","111","011","010","110","100"], ["000","010","011","001","101","111","110","100"], .....]

only one bit change between members.

please help.

this gives only one

g 0 = [""]
g n = (map ('0':)) (g (n-1)) ++ (map ('1':)) (reverse (g (n-1)))

gray code is true for this.but ı want to find all combinations.

how can I generate all possible gray codes for given n number?

permute [] = [[]]
permute xs = concatMap (\x -> map (x:) $ permute $ delete x xs) xs 
g 0 = [""]
g n = (map ('0':)) (g (n-1)) ++ (map ('1':)) (reverse (g (n-1)))
oneBitAll n = (map transpose . permute . transpose $ g n)

This code generate half of possibilities.What can ı add this code?this code generates;

[["000","001","011","010","110","111","101","100"],["000","010","011","001","101","111","110","100"],["000","001","101","100","110","111","011","010"],["000","010","110","100","101","111","011","001"],["000","100","101","001","011","111","110","010"],["000","100","110","010","011","111","101","001"]]

but must generate 12 members.

Solution

There is probably a smarter way to do this that exploits more of the structure of gray codes. This way is sort of quick and dirty, but it seems to work fairly well.

The basic idea is we'll generate all sequences of bitstrings, then filter out the ones that aren't gray codes. We'll be slightly more clever, though, in that we'll check prefixes of each sequence to make sure they could plausibly be extended to a gray code, and prune prefixes that can't be.

For our purposes, a gray code will have five properties:

Each pair of consecutive bitstrings differs in exactly one place.
The sequence is cyclic: the first and last bitstring also differ in exactly one place.
No two bitstrings in a sequence are equal.
A code with bitstring length n has 2^n elements.
To break the cyclic symmetry, every code will start with the all-zero bitstring.

Three of these properties can be expressed on code prefixes:

import Control.Monad
import Data.List

validCodePrefix xss = nearbyPairs && unique && endsWithZeros where
    nearbyPairs = all (uncurry nearby) (zip xss (tail xss))
    unique = all ((1==) . length) . group . sort $ xss
    endsWithZeros = all (all (=='0')) (take 1 (reverse xss))

nearby xs xs' = length [() | (x, x') <- zip xs xs', x /= x'] == 1

The cyclic condition applies only to completed codes, and can be written as:

cyclic xss = nearby (head xss) (last xss)

We can implement the search and enforce the length condition at the same time, by repeatedly choosing from all appropriate length bitstrings, and keeping only those ones that are valid:

codes n = go (2^n) [] where
    go 0 code = [reverse code | cyclic code]
    go i code = do
        continuation <- replicateM n "01"
        guard (validCodePrefix (continuation:code))
        go (i-1) (continuation:code)