Binary Reflected Gray Code generation recursively

Question

I tried to write BRGC recursively. I've really recognized that intrinsic of recursion helps for some problems in which I think BRGC is included. is the way I wrote it recursively adequate solution? Can it be improved w.r.t recursion?

Do both methods have same complexity Theta(n), right? T(n) = T(n-1) + n, T(n) = T(n/2) + n respectively.

import java.util.ArrayList;
import java.util.List;

class Test {
    public static void main(String[] args) {
        System.out.println(genGray(List.of("0", "1"), 3));
        System.out.println(genGrayV2(List.of("0", "1"), (int)Math.pow(2, 3)));
    }

    public static List<String> genGray(List<String> list, int n) {
        if (list.size() == (int)Math.pow(2, n+1))
            return list;

        List<String> combinedList = new ArrayList<>();

        for (String elem : list) {
            combinedList.add("0" + elem);
        }

        for (String elem : list) {
            combinedList.add("1" + elem);
        }


        return genGray(combinedList, n);
    }

    public static List<String> genGrayV2(List<String> list, int n) {
        if (n == 1)
            return list;

        List<String> combinedList = new ArrayList<>();

        for (String elem : list) {
            combinedList.add("0" + elem);
        }

        for (String elem : list) {
            combinedList.add("1" + elem);
        }

        return genGray(combinedList, n / 2);
    }
}

Vogel612 · Accepted Answer · 2018-12-04 12:57:16Z

Not Gray Code

The first big issue with this code that I see is naming things. Naming a list list adds absolutely no semantic information. You're duplicating what the "syntax" already tells you. n also doesn't tell us anything. Let's try the following:

public static List<String> generateGray(List<String> currentGrayWords, int targetBitLength) {

public static List<String> generateGrayV2(List<String> currentGrayWords, int wordsToGenerate) {

Note that the semantics of these two methods are not interchangeable. There's quite a few assumptions you make about how parameters are passed in. The first assumption is that you think that the "currentGrayWords" are a valid and complete BRGC (and non-empty). The second assumption is that n is a clean power of two in the first version and positive in both versions.

Check your assumptions. Consider the following invocations that look completely harmless but generate totally unintended results:

generateGray(Collections.emptyList(), 8); // returns empty list
generateGray(Arrays.asList("0", "01", "10", "1"), 4); // returns inconsistent gray code
generateGray(Arrays.asList("0", "1"), 5); // stackoverflow because recursion never terminates
generateGrayV2(Arrays.asList("000", "001", "011", "010", "110", "111", "101", "100"), -4);
// stackoverflow, because it never terminates

Gray Code

As it stands your code isn't even correct. Wikipedia tells me that a binary reflected gray code works by concatenating the original list with each element having 0 prepended and the reflected original list with each element having 1 prepended. That reflection is conspiciously absent in the code you present here.

As such the following is what your code creates:

genGray(Collections.singletonList(""), 8);
"0" "1"
"00" "01" "10" "11" // gray-code property violated
"000" "001" "010" "011" "100" "101" "110" "111"

The correct sequence would've been:

"0" "1"
"00" "01" "11" "10"
"000" "001" "011" "010" "110" "111" "101" "100"

Method

What this code is missing is a comprehensive test-suite that actually checks inputs that you didn't consider when first writing this code. You may want to not expose the List<String> as input parameter. It could (should?) be something internal to what the code does.

Try to break your code! If you don't succeed, try harder. Throw things at it that "nobody would ever think of doing". That way when somebody actually does, the code handles it gracefully.

With recursion it's especially important to think of the "termination condition" in your code. Make sure whatever is thrown into the method, it always terminates. Stack Overflows are not an acceptable result ...

Thank you so much for your brilliant criticism. However, I don't understand what you mean by saying You may want to not expose the List<String> as input parameter. It could (should?) be something internal to what the code does. Could you explain it a bit more? By the way, yes it's needed to reflect to get right order for 1s and 0s yet I just took into consideration to calculate whole possible subsets. — Soner from The Ottoman Empire
– Soner from The Ottoman Empire, Commented Dec 4, 2018 at 14:08
@itsnotmyrealname what I mean is that the argument is a vector for unaware users of the API to make mistakes they won't notice easily. I don't think that exposing the parameter makes a lot of sense from a consumer perspective. As such it's an internal detail of how your code works and shouldn't be visible on a public entry-point... — Vogel612
– Vogel612, Commented Dec 4, 2018 at 21:33

Stack Exchange Network

Binary Reflected Gray Code generation recursively

1 Answer 1

Not Gray Code

Gray Code

Method

You must log in to answer this question.

Hot Network Questions

Binary Reflected Gray Code generation recursively

1 Answer 1

Not Gray Code

Gray Code

Method

You must log in to answer this question.

Related

Hot Network Questions