BinaryListProblem.java

package com.bringholm.javatest;


import java.math.BigInteger;
import java.util.HashMap;
import java.util.Objects;

public class BinaryListProblem {
    private static HashMap<BinomialCoefficient, BigInteger> binomialCoefficients = new HashMap<>();

    public static void main(String[] string) {
        BigInteger[] ints = numberOfOnes(new BigInteger("10402927437586948002"), 64);
        BigInteger number = getNumber(ints[0].intValue(), ints[1], 64);
        System.out.println(number.toString());
    }

    // Ta reda på talet när man vet hur många ettor det har.
    private static BigInteger getNumber(int ones, BigInteger relativeIndex, int length) {
        StringBuilder number = new StringBuilder();
        for (int i = 1; i <= length; i++) {
            if (length == ones) {
                while (number.length() < length) {
                    number.append("1");
                }
                break;
            }
            BigInteger coefficient = binomialCoefficient(length - i, ones);
            if (relativeIndex.compareTo(coefficient) < 0) {
                number.append("0");
            } else {
                number.append("1");
                ones--;
                relativeIndex = relativeIndex.subtract(coefficient);
            }
            if (ones == 0) {
                while (number.length() < length) {
                    number.append("0");
                }
                break;
            }
            if (ones == length - i) {
                while (number.length() < length) {
                    number.append("1");
                }
                break;
            }
        }
        System.out.println(number);
        return new BigInteger(number.toString(), 2);
    }

    // Ta reda på hur många ettor talet innehåller
    private static BigInteger[] numberOfOnes(BigInteger index, int length) {
        BigInteger currentIndex = BigInteger.ZERO;
        BigInteger prevIndex = BigInteger.ZERO;
        for (int i = 0; i <= length; i++) {
            if (index.compareTo(currentIndex) < 0) {
                //System.out.println(i - 1 + " ettor, index " + index.subtract(prevIndex) + " bland dessa");
                return new BigInteger[] {BigInteger.valueOf(i - 1), index.subtract(prevIndex)};
            } else if (index.compareTo(currentIndex) == 0) {
                //System.out.println(i + " ettor, index 0 bland dessa");
                return new BigInteger[] {BigInteger.valueOf(i), BigInteger.ZERO};
            }
            prevIndex = currentIndex;
            currentIndex = currentIndex.add(binomialCoefficient(length, i));
        }
        return new BigInteger[0];
    }

    private static BigInteger binomialCoefficient(int n, int k) {
        BinomialCoefficient coeff = new BinomialCoefficient(n, k);
        if (binomialCoefficients.containsKey(coeff)) {
            return binomialCoefficients.get(coeff);
        }
        BigInteger coefficient;
        if (k == 0) {
            coefficient = BigInteger.ONE;
        } else {
            if (k > n - k) {
                k = n - k;
            }
            BigInteger numerator = BigInteger.ONE;
            BigInteger denominator = BigInteger.ONE;
            for (int i = 1; i <= k; i++) {
                numerator = numerator.multiply(BigInteger.valueOf(n + 1 - i));
                denominator = denominator.multiply(BigInteger.valueOf(i));
            }
            coefficient = numerator.divide(denominator);
        }
        binomialCoefficients.put(coeff, coefficient);
        return coefficient;
    }

    private static class BinomialCoefficient {
        private int n;
        private int k;

        BinomialCoefficient(int n, int k) {

        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (obj instanceof BinomialCoefficient) {
                return false;
            } else {
                //noinspection ConstantConditions
                return ((BinomialCoefficient) obj).n == this.n && ((BinomialCoefficient) obj).k == this.k;
            }
        }

        @Override
        public int hashCode() {
            return Objects.hash(n, k);
        }
    }
}