math - 我能以多简洁的方式表示 1024 到 1024 的排列？

Question

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

我有什么选择？

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

经典的排列理论应该告诉我可能性的数量 - nPr(顺序很重要，没有重复)。但这个数字太大了，它困扰着我的小大脑，压垮了我的 dec<->bin 计算器。如果我这样做的话，我会得到更少的比特吗？ (为什么不呢？数学很糟糕啊？)

Java 代码的奖励点，这样我就可以修改 n 和 r 来找到所需的位数以及基数 64 位数。 :-)

PS。这是对我严肃的投票系统提案的可行性测试，该投票系统使用纸张进行审计跟踪，并使用计算机进行快速计数。

Answer 1

Wolfram 阿尔法 will tell you最佳表示需要 ⌈log₂(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();
    }
}