2

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

我有哪些选择？

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

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

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

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

4

1 回答 1

3

Wolfram alpha会告诉您，您需要 ⌈log 2 (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();
    }
}
于 2013-09-12T07:50:49.913 回答