Saturday, December 28, 2013

Fun with Guava: Cross joining two iterables, binary functions vs pairs, and reconstructing inorder traversals from preorder and postorder

Suppose you have the following interface for a binary function:
interface BiFunction<L, R, T> {
    T apply(L left, R right);
}
Then you also have these utility methods:
public static <L, R, T> Function<R, T> fixLeft(
        final BiFunction<? super L, ? super R, ? extends T> f2,
        final L left
    ) {
    
    return new Function<R, T>() {
        @Override
        public T apply(R right) {
            return f2.apply(left, right);
        }
    };
}
    
public static <L, R, T> FluentIterable<T> crossJoin(
        final Iterable<? extends L> lefts,
        final Iterable<? extends R> rights,
        final BiFunction<? super L, ? super R, ? extends T> joiner
    ) {
    
    return FluentIterable.from(lefts).transformAndConcat(
        new Function<L, FluentIterable<T>>() {
            @Override
            public FluentIterable<T> apply(final L left) {
                return FluentIterable.from(rights).transform(fixLeft(joiner, left));
            }
        }
    );
}

public static FluentIterable<Integer> zeroToN(int n) {
    return FluentIterable.from(
        ContiguousSet.create(
            Range.closed(0,  n),
            DiscreteDomain.integers()
        )
    );
}
Then you can do the following:
System.out.println(
    crossJoin(
        ImmutableList.of('a', 'b', 'c'),
        zeroToN(3),
        new BiFunction<Character, Integer, String>() {
            @Override
            public String apply(Character letter, Integer count) {
                return "{" + Strings.repeat(String.valueOf(letter), count) + "}";
            }
        }
    )
);
// [{}, {a}, {aa}, {aaa}, {}, {b}, {bb}, {bbb}, {}, {c}, {cc}, {ccc}]
Note that there's an implicit pairing in the cross join, and if (for better or for worse) a Pair<L, R> type is made available, one would be tempted to write the obvious BiFunction<L, R, Pair<L, R>> pairing binary function and run wild with it. It seems that in this particular use case at least, the use of binary function as an alternative to using pairs as an intermediate step doesn't look that bad. Anyway, it's perhaps also worth mentioning that Java 8 still will not have a pair type, but it will have a binary function type.
As one more example, here's another fun thing you can do with the above: given the preorder and postorder traversals of some unknown binary tree T, try to reconstruct T and return its inorder traversal. If there are multiple solutions, then return all of them. Here's one way to solve it:
interface BinaryOp<T> extends BiFunction<T, T, T> {
}

public static Iterable<String> inorderReconstruction(final String preorder, final String postorder) {
    if (preorder.isEmpty()) {
        return Collections.singleton("");
    }
    final int n = preorder.length() - 1;
    final char root = preorder.charAt(0);
    if (postorder.charAt(n) != root) {
        return Collections.emptyList();
    }
        
    return zeroToN(n).transformAndConcat(
        new Function<Integer, Iterable<String>>() {
            @Override
            public Iterable<String> apply(Integer k) {
                return crossJoin(
                    inorderReconstruction(preorder.substring(1, k + 1), postorder.substring(0, k)),
                    inorderReconstruction(preorder.substring(k + 1),    postorder.substring(k, n)),
                    new BinaryOp<String>() {
                        @Override
                        public String apply(String left, String right) {
                            return "(" + left + root + right + ")";
                        }
                    }
                );
            }
        }
    );
}    
Thus:
System.out.println(
    inorderReconstruction("123", "321")
); // [(1(2(3))), (1((3)2)), ((2(3))1), (((3)2)1)]

System.out.println(
    inorderReconstruction("12345", "34251")
); // [(((3)2(4))1(5))]
The reconstruction is done lazily, as demonstrated here:
String x13 = Strings.repeat("x", 13);
FluentIterable<String> allBinaryTreesOfSize13 =
    FluentIterable.from(
        inorderReconstruction(x13, x13)   // FAST!!
    );
  
System.out.println(
    allBinaryTreesOfSize13.size()         // SLOW!!
); // 742900 == Catalan(13)

System.out.println(
    allBinaryTreesOfSize13.limit(2)       // FAST!!
); // [(x(x(x(x(x(x(x(x(x(x(x(x(x))))))))))))), (x(x(x(x(x(x(x(x(x(x(x((x)x))))))))))))]
The last line also provides an easy and fast way to check for uniqueness of solution: get up to 2, and then verify that there's exactly 1.

20 comments:

  1. You are doing a great job. I would like to appreciate your work for good accuracy
    Regards,
    PHP Training in Chennai | PHP Course in Chennai

    ReplyDelete
  2. I found your this post while searching for some related information on blog search...Its a good post..keep posting and update the information. recover money lost to binary options

    ReplyDelete
  3. keep up the good work. this is an Assam post. this to helpful, i have reading here all post. i am impressed. thank you. this is our digital marketing training center. This is an online certificate course
    digital marketing training in bangalore | https://www.excelr.com/digital-marketing-training-in-bangalore

    ReplyDelete
  4. i never know the use of adobe shadow until i saw this post. thank you for this! this is very helpful. Pocket Option No deposit Bonus

    ReplyDelete
  5. Excellent and very exciting site. Love to watch. Keep Rocking. camping mit kind und hund

    ReplyDelete
  6. Thanks of sharing this post…Python is the fastest growing language that helps to get your dream job in a developing area. It says every fundamental in a programming, so if you want to become an expertise in python get some training








    Dot Net Training in Chennai | Dot Net Training in anna nagar | Dot Net Training in omr | Dot Net Training in porur | Dot Net Training in tambaram | Dot Net Training in velachery

    ReplyDelete
  7. Binary Options Strategy PDF are relatively easier to understand than traditional options. However, it is important to know at least a binary options strategy in order to maximize your possible payouts.

    ReplyDelete
  8. Wow those look great. I need to bring some cakes for our last day in the office so might have to give that recipe a try.https://binaryoptionsdemo.com

    ReplyDelete
  9. You'll have the option to increase significant Forex market understanding, safeguard your own connections and above all bring in cash in Forex exchanging while you figure out how to exchange Forex. Farah

    ReplyDelete
  10. We have sell some products of different custom boxes.it is very useful and very low price please visits this site thanks and please share this post with your friends. sinais iq option

    ReplyDelete
  11. I read that Post and got it fine and informative. robo iq option

    ReplyDelete
  12. Online day exchanging is the most dynamic kind of exchanging. Informal investors' exchanging span doesn't surpasses one day. forex course etc

    ReplyDelete