Генерировать двоичное однобитовое изменение между всеми членами

Question

У меня вопрос. Я хочу создать двоичный список. Но между членами списка будет только одно изменение бит.

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

для n=2

Выход:

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

п = 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 членов.

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)