-2

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

oneBitAll :: Integral 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)))

格雷码适用于此。但我想找到所有组合。

如何为给定的 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)

此代码生成一半的可能性。我可以添加此代码什么？此代码生成；

[["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 个成员。

4

1 回答 1

0

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

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

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

  • 每对连续的位串在一个地方完全不同。
  • 该序列是循环的：第一个和最后一个位串也恰好在一个地方不同。
  • 序列中没有两个位串是相等的。
  • 位串长度为 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)
于 2016-05-27T16:19:58.990 回答