generating a binary sequence

Question

I need to generate a binary sequence of keys where each key is of length 'x',and each key is generated by a specific operation on the previous key.
So assuming the key length to be 3,I should be able to generate a sequence as(illustration):

001 010 100 011 .....

Each key has to be derived by some bit operation on the previous key,till we have exhausted all possible permutations for that specific key length.
Since I am a newbie on bit operations - is this a possible operation;and how do we generate this sequence for any given length.
I would prefer an example in java - but the idea is to understand the logic and the specific oepration.

Answer 1

You probably want to look for pseudo-random generators if the progression has to be a fixed bit operation. You might be interested in grey codes too.

Answer 2

Here are two approaches in Java:

Iterative:

Start from 0 to 2^length and convert each number to binary string padded with zeroes in front.

public static List<String> binarySequence(final int length) {
    final int noOfItems = 1 << length;
    final List<String> sequences = new ArrayList<>(noOfItems);
    final String format = "%" + length + "s";
    for (int num = 0; num < noOfItems; num++) {
        final String binary = String.format(format,
                Integer.toBinaryString(num)).replace(' ', '0');
        sequences.add(binary);
    }
    return sequences;
}

Recursive:

Base case (length 1), Only two values: 0 and 1. For length > 1, prepend 0 and 1 to the sequences from previous recursion. For example, for length of 2, prepending 0 and 1 to the previous recursion output(0, 1): 00, 01, 10, 11.

public static List<String> binarySequenceRecur(final int length) {
    final List<String> sequences;
    if (length <= 1) {
        sequences = Arrays.asList("0", "1");
    } else {
        final List<String> prevSequences = binarySequence(length - 1);
        final LinkedList<String> seqs = new LinkedList<>();
        for (final String seq: prevSequences) {
            seqs.addLast("0" + seq);
        }
        for (final String seq: prevSequences) {
            seqs.addLast("1" + seq);
        }
        sequences = seqs;
    }
    return sequences;
}