math - 我可以多么简洁地表示 1024 从 1024 的排列？

Question

我想给我的用户一个简洁的 base-64 字母数字代码，以代表他们在从 1024 名候选人的选票中按顺序选择 1024 名候选人时所做的选择。 (这是最坏的情况......我可能可以忍受 < 256)。

我有哪些选择？

一种天真的方法告诉我，如果 1024 个元素中的每一个都可以用唯一的序数 (2 ^ 10) 表示，并且我需要一系列 1024 个序数，那么 10 位 x 1024 个位置 = 10,240 位就可以了。但这仍然是 1707 基 64 位，比我希望的要长一点，感觉就像我在浪费 9 位来表示“1”(尽管我可能错了)。

经典置换理论应该告诉我可能性的数量 - nPr(顺序很重要，没有重复)。但是这个数字太大了，它困扰着我的小脑袋，压倒了我的 dec<->bin 计算器。如果我这样做，我会得到更少的位吗？ (为什么不呢？数学很烂，嗯？)

Java 代码的加分点，因此我可以修改 n 和 r 以找到所需的位数以及基数 64 位数。 :-)

附注。这是对我关于使用纸张进行审计跟踪和使用计算机进行快速计数的投票系统的严肃提案的可行性测试。

Answer 1

Wolfram alpha will tell you在最佳表示中，您需要 ⌈log2(1024!)⌉=8,770 位。并不比天真地存储元素本身好多少。实现这种稍微简洁的表示的概念上最简单的方法是想象所有这些按字典顺序排列的排列。然后您可以简单地将排列的索引存储在该列表中。为了实现这一点，您可以迭代排列的元素，并在每个位置问自己有多少排列具有所有前面的位置共同，但在当前位置的值较小。将这些数字相加将导致排列的从零开始的索引。

由于您为此询问了 Java 代码，因此这里有一段代码将确定所需的位数，并且还将计算给定排列的简明表示。

import java.math.BigInteger;
class SO18757672 {
    int n;
    BigInteger[] fac;
    SO18757672(int n) {
        this.n = n;
        fac = new BigInteger[n + 1];
        fac[0] = BigInteger.ONE;
        for (int i = 1; i <= n; ++i)
            fac[i] = fac[i - 1].multiply(BigInteger.valueOf(i));
    }
    int bitsRequired() {
        return fac[n].subtract(BigInteger.ONE).bitLength();
    }
    BigInteger codeFor(int[] permutation) {
        if (permutation.length != n)
            throw new IllegalArgumentException("wrong length");
        BigInteger res = BigInteger.ZERO;
        for (int i = 0; i != n; ++i) {
            int pi = permutation[i];
            if (pi < 0 || pi > n - i)
                throw new IllegalArgumentException("invalid value");
            res = res.add(fac[n - 1 - i].multiply(BigInteger.valueOf(pi)));
            for (int j = i + 1; j != n; ++j) {
                if (permutation[j] == pi)
                    throw new IllegalArgumentException("duplicate value");
                if (permutation[j] > pi)
                    --permutation[j]; // We modify out input!
            }
        }
        return res;
    }
    boolean sanityChecks() {
        int[] p = new int[n];
        // smallest code is zero, for all elements in order
        for (int i = 0; i != n; ++i)
            p[i] = i;
        assert BigInteger.ZERO.equals(codeFor(p));
        // largest code is n!-1, for all elements in reverse order
        for (int i = 0; i != n; ++i)
            p[i] = n - 1 - i;
        assert fac[n].subtract(BigInteger.ONE).equals(codeFor(p));
        return true; // so we can use this in an assert call
    }
    public static void main(String[] args) {
        SO18757672 instance = new SO18757672(1024);
        System.out.println(instance.bitsRequired() + " bits required");
        assert instance.sanityChecks();
    }
}