Consider all possible N-bit binary configurations. Your task is to find a permutation of these values such that any two consecutive configurations differ by exactly one bit. If there are multiple solutions, all of them are considered correct.
Input
A single integer: N
Output
The output should contain all 2N configurations, each on a separate line.
Each configuration should consist of exactly N bits, including leading zeros.
Constraints
- 1 ≤ N ≤ 12
Sample
| Input | Output |
|---|---|
| 3 | 000 001 011 010 110 100 101 111 |
Approach #1
Start with the values [0, 1]. At each iteration, do the following:
- reverse the current list and append it to itself
- prepend each element in the first half with a 0
- prepend each element in the second half with a 1
| #1 | #2 | #3 | #4 |
|---|---|---|---|
| 0 1 | 00 01 11 10 | 000 001 011 010 110 111 101 100 | 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
The Nth iteration of this process generates all N bit configurations, in an order which respects the required property.
Haskell implementation
once applies a single iteration to a given list.
solve uses function composition to generate once composed to itself N-1 times, and applies the resulting function to the first iteration.
solve n = foldr (.) id (replicate (n-1) once) ["0", "1"] once xs = map ('0':) xs ++ map ('1':) (reverse xs) main = do input <- getContents let n = read input :: Int sequence $ map putStrLn $ solve n
Approach #2
Start from the null configuration. Try each of the N possible bit flips, and keep track of previously encountered configurations. When a new configuration is found, repeat the same process for it. Stop when no new configuration can be found.
Note: a recursive implementation of this approach can result in a stack overflow.
