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.

Just start with all zeroes, stop on all ones, and add one each time. — David Schwartz
– David Schwartz, Commented Aug 17, 2013 at 3:46
Java has bitwise operators (see docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html) — SheetJS
– SheetJS, Commented Aug 17, 2013 at 3:52
I get the idea now - thanks.So it goes 000 + 1=>001 + 1=>010 + 1.... till we reach 111. A java function will help ,since this is not what I do often. — IUnknown
– IUnknown, Commented Aug 17, 2013 at 4:01
I think this is what will help me achieve what I needed - stackoverflow.com/questions/8548586/adding-binary-numbers. — IUnknown
– IUnknown, Commented Aug 17, 2013 at 4:17

jcoppens · Accepted Answer · 2013-08-17 03:53:26Z

0

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.

answered Aug 17, 2013 at 3:53

jcoppens

5,4726 gold badges32 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marimuthu Madasamy · Accepted Answer · 2013-08-17 06:11:59Z

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;
}

Collectives™ on Stack Overflow

generating a binary sequence

2 Answers 2

Comments

Iterative:

Recursive:

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Iterative:

Recursive:

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related