Optimal single-elimination bracket ordering

bracket_ordering.py

#
# Copyright 2022 Deephaven Data Labs
# 
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#

def bracket_optimal_seed_order(num_rounds):
    '''
    Generates the bracket-optimal 1-based seed ordering for a bracket with num_rounds rounds.

    Optimal means that none of the top 2^p ranked players can meet earlier than the p-th from last round of the competition.

    See <a href="https://oeis.org/A208569">The Online Encyclopedia of Integer Sequences - A208569</a>
    '''
    L = 2 ** num_rounds
    return [t(L, i + 1) for i in range(L)]

def t(L, k):
    if k == 1:
        return 1
    m = (k - 1) & -(k - 1)
    return 1 + L // m - t(L, k - m)

BracketOrdering.java

/*
 * Copyright 2022 Deephaven Data Labs
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import java.util.List;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class BracketOrdering {

    /**
     * Generates the bracket-optimal 1-based seed ordering for a bracket with {@code n} rounds.
     *
     * <p>
     * Optimal means that none of the top {@code 2^p} ranked players can meet earlier than the {@code p-th} from last
     * round of the competition.
     *
     * @param n the number of rounds
     * @return the 1-based seed ordering, with {@code 2^n} elements
     * @see <a href="https://oeis.org/A208569">The Online Encyclopedia of Integer Sequences - A208569</a>
     */
    public static IntStream bracketOptimalSeedOrder(int n) {
        final int L = 1 << n;
        return IntStream.rangeClosed(1, L).map(i -> t(L, i));
    }

    /**
     * Generates the bracket-optimal ordering for the seed-ordered {@code items}.
     *
     * <p>
     * Optimal means that none of the top {@code 2^p} ranked players can meet earlier than the {@code p-th} from last
     * round of the competition.
     *
     * @param items the items in seed-order, must have a power-of-2 size
     * @param <T> the type
     * @return the items in bracket-optimal order
     * @see <a href="https://oeis.org/A208569">The Online Encyclopedia of Integer Sequences - A208569</a>
     */
    public static <T> Stream<T> bracketOptimalOrder(List<T> items) {
        final int L = items.size();
        if ((L & (L - 1)) != 0) {
            throw new IllegalArgumentException("items must have a power-of-2 size");
        }
        return IntStream.rangeClosed(1, L).map(i -> t(L, i) - 1).mapToObj(items::get);
    }

    private static int t(int L, int k) {
        if (k == 1) {
            return 1;
        }
        // a(n) = a & (-a)
        // https://oeis.org/A006519
        int k1 = k - 1;
        int m = k1 & (-k1);
        return 1 + L / m - t(L, k - m);
    }

    public static void main(String[] args) {
        final int numRounds = args.length == 0 ? 4 : Integer.parseInt(args[0]);
        bracketOptimalSeedOrder(numRounds).forEachOrdered(System.out::println);
    }
}