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

Question

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

oneBitAll :: Интеграл а => а -> [[String]]

при п = 2

Выход:

[ "00", "01", "11", "10"] в [ "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, «100», «010», «011», «001», «101», «100», «010», , "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) 

Этот код генерирует половину возможностей. Что не может добавить этот код?

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

Возможно, существует более разумный способ сделать это, что использует большую часть структуры серых кодов. Этот способ довольно быстрый и грязный, но, похоже, он работает достаточно хорошо.

Основная идея заключается в том, что мы будем генерировать все последовательности битовых строк, а затем отфильтровывать те, которые не являются серыми кодами. Тем не менее, мы будем немного умнее, потому что мы проверим префиксы каждой последовательности, чтобы убедиться, что они могут быть расширены до серого кода и обрезать префиксы, которых не может быть.

Для наших целей, серый код будет иметь пять свойств:

• Каждая пара последовательных bitstrings отличается точно в одном месте.
• Последовательность циклическая: первая и последняя битстрона также различаются в одном месте.
• Нет двух битовых строк в последовательности.
• Код с длиной битовой строки 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)