2

ユーザーに、1024 人の候補者の投票から順番に 1024 人の候補者を選ぶ際の選択を表す、簡潔な base-64 の英数字コードを提供したいと考えています。(これは最悪のケースです...おそらく < 256 で十分です)。

私のオプションは何ですか？

単純なアプローチでは、1024 個の要素のそれぞれを一意の序数 (2 ^ 10) で表すことができ、一連の 1024 個の序数が必要な場合、10 ビット x 1024 位置 = 10,240 ビットでうまくいくことがわかります。しかし、それはまだ 1707 基数 64 桁であり、これは私が望んでいたよりも少し長く、'1' を表すためにビット 9 ビットを無駄にしているように感じます (ただし、おそらくそれについては間違っています)。

古典的な順列理論は、可能性の数を教えてくれるはずです-nPr（順序は重要で、重複はありません）。しかし、その数は非常に大きく、私の小さな脳を悩ませ、dec<->bin 計算機を圧倒します。このようにすると、ビット数が少なくなりますか? （なぜですか？数学は最悪ですよね？）

Javaコードのボーナスポイントなので、nとrをいじって、必要なビット数と基数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 に答える