질문이 있습니다. 이진 목록을 생성하고 싶지만 목록의 구성원 간에는 한 비트 만 변경됩니다.
oneBitAll :: 적분 a => a-> [[문자열]]
n = 2 인 경우
산출:
[ "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 "], .....]
멤버간에 단 한 비트 만 변경됩니다.
도와주세요.
이것은 하나만 준다
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 명의 구성원을 생성해야합니다.
그레이 코드 구조를 더 많이 이용하는 더 현명한 방법이있을 것입니다. 이 방법은 빠르고 더럽지 만 꽤 잘 작동하는 것 같습니다.
기본 아이디어는 모든 비트 문자열 시퀀스를 생성 한 다음 회색 코드가 아닌 것을 필터링하는 것입니다. 그러나 우리는 각 시퀀스의 접두사를 확인하여 그레이 코드로 확장 할 수 있는지 확인하고 불가능한 접두사를 제거한다는 점에서 약간 더 영리 할 것입니다.
우리의 목적을 위해 회색 코드에는 5 가지 속성이 있습니다.
이러한 속성 중 세 가지를 코드 접두사로 표현할 수 있습니다.
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)
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다