在所有成员之间生成二进制一位变化

Question

我有一个问题。我想生成二进制列表。但是列表成员之间只有一位变化。

oneBitAll :: 积分 a => a -> [[String]]

n=2

输出：

["00","01","11","10"] 已经 ["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"], .....]

成员之间只有一位变化。

请帮忙。

这只给了一个

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

灰色代码适用于 this.but 我想找到所有组合。

如何为给定的 n 个数字生成所有可能的格雷码？

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)

此代码生成一半 possibilities.What 我可以添加此代码吗？此代码生成；

[["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"]]

但必须生成 12 个成员。

Answer 1

可能有一种更聪明的方法可以利用更多的格雷码结构来做到这一点。这种方法有点快而且脏，但它似乎工作得很好。

基本思想是我们将生成所有位串序列，然后过滤掉不是格雷码的位串。不过，我们会稍微聪明一些，因为我们将检查每个序列的前缀，以确保它们可以合理地扩展为格雷码，并修剪不能扩展的前缀。

为了我们的目的，格雷码将具有五个属性：

每对连续的位串恰好有一处不同。
序列是循环的：第一个和最后一个位串也恰好有一处不同。
序列中没有两个位串是相等的。
位串长度为 n 的代码有 2^n 个元素。
为了打破循环对称性，每个代码都将以全零位串开始。

这些属性中的三个可以用代码前缀表示：

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

循环条件只适用于完成的代码，可以写成：

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

我们可以通过从所有适当长度的位串中重复选择并仅保留那些有效的位串来同时执行搜索和强制执行长度条件：

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)

在所有成员之间生成二进制一位变化

generate binary one bit change between all members

haskell

gray-code