ما هي طريقة جيدة لتنفيذ اختيار التدوين في جافا؟

Question

... يفضل في جافا. هنا ما لدي:

//x choose y
public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y == 0 || y == x) return 1;

    double answer = 1;
    for (int i = x-y+1; i <= x; i++) {
        answer = answer * i;
    }
    for (int j = y; j > 1; j--) {
        answer = answer / j;
    }
    return answer;
}

أتساءل عما إذا كانت هناك طريقة أفضل للقيام بذلك؟

Answer 1

اختر (ن، ك) = ن! / (NK)! ك!

يمكنك القيام بشيء مثل هذا في O (K):

public static double choose(int x, int y) {
    if (y < 0 || y > x) return 0;
    if (y > x/2) {
        // choose(n,k) == choose(n,n-k), 
        // so this could save a little effort
        y = x - y;
    }

    double denominator = 1.0, numerator = 1.0;
    for (int i = 1; i <= y; i++) {
        denominator *= i;
        numerator *= (x + 1 - i);
    }
    return numerator / denominator;
}

تعديل إذا x و y كبيرة، سوف تتجاوز ببطء أكثر ببطء (أي آمنة لقيم x & y الأكبر) إذا قمت بتقسيم إجابتك عندما تذهب معك:

    double answer = 1.0;
    for (int i = 1; i <= y; i++) {
        answer *= (x + 1 - i);
        answer /= i;           // humor 280z80
    }
    return answer;

Answer 2

الأرقام التي تتعامل معها سوف تصبح كبيرة جدا وسوف تتجاوز بسرعة دقة double القيم، مما يمنحك نتائج خاطئة بشكل غير متوقع. لهذا السبب قد ترغب في النظر في حل تعسفي الدقة مثل استخدام java.math.BigInteger, ، والتي لن تعاني من هذه المشكلة.

Answer 3

ما لديك يبدو واضحا بالنسبة لي، ليكون صادقا. من المسلم به أن أضع بيانات العودة في الأقواس لأن هذه الاتفاقية التي أتبعها، ولكن بصرف النظر عن ذلك يبدو جيدا كما يحصل.

أعتقد أنني ربما عكس ترتيب الحلقة الثانية، بحيث تصاعدي كلا الحلقتين.

كما يقول جريج، إذا كنت بحاجة إلى الحصول على إجابات دقيقة للأرقام الكبيرة، يجب عليك التفكير في أنواع البيانات البديلة. بالنظر إلى أن النتيجة يجب أن تكون دائما عدد صحيح، فقد ترغب في اختيار BigInteger (على الرغم من كل الانقسامات، ستكون النتيجة عددا صحيحا دائما):

public static BigInteger choose(int x, int y) {
    if (y < 0 || y > x) 
       return BigInteger.ZERO;
    if (y == 0 || y == x) 
       return BigInteger.ONE;

    BigInteger answer = BigInteger.ONE;
    for (int i = x - y + 1; i <= x; i++) {
        answer = answer.multiply(BigInteger.valueOf(i));
    }
    for (int j = 1; j <= y; j++) {
        answer = answer.divide(BigInteger.valueOf(j));
    }
    return answer;
}

Answer 4

ترميز هذا في C #، لكنني حاولت أن أجعلها قابلة للتطبيق قدر الإمكان إلى Java.

اشتق من بعض هذه المصادر، بالإضافة إلى زوجين أشياء صغيرة مني.

• http://blog.plover.com/math/choose.html.
• http://blog.plover.com/math/choose-2.html.

رمز:

public static long BinomialCoefficient(long n, long k)
{
    if (n / 2 < k)
        return BinomialCoefficient(n, n - k);

    if (k > n)
        return 0;

    if (k == 0)
        return 1;

    long result = n;
    for (long d = 2; d <= k; d++)
    {
        long gcd = (long)BigInteger.GreatestCommonDivisor(d, n);
        result *= (n / gcd);
        result /= (d / gcd);
        n++;
    }

    return result;
}

Answer 5

بالنسبة

ن! / ((R!) (NR)!)

استخدم هذا (pseudocode)

if (R>N) return 0;

long r = max(R, N-r)+1;
if (R==N) return 1;

for (long m = r+1, long d = 2; m <= N; m++, d++ ) {
    r *= m;
    r /= d;
}
return r;

Answer 6

هذا الإصدار لا يتطلب BigInteger أو الحساب العائم والأعمال دون أخطاء تجاوز الفضاء للجميع n أقل من 62. 62 أكثر من 28 هو أول زوج يؤدي إلى تجاوز.

public static long nChooseK(int n, int k) {
    k = Math.min(k, n - k);

    if (n < 0 || k < 0)
        throw new IllegalArgumentException();

    if (k == 0)
        return 1;

    long value = n--;

    for (int i = 2; i <= k; i++) {
        value = Math.multiplyExact(value, n--);
        value /= i;
    }

    return value;
}

يثبت الاختبار التالي أن هذا صحيح:

@Test
void nChooseKLongVsBigInt() {
    for (int n = 0; n < 62; n++) {
        for (int k = 0; k <= n; k++) {
            assertEquals(nChooseKBigInt(n, k), BigInteger.valueOf(nChooseK(n, k)));
        }
    }
}

private BigInteger nChooseKBigInt(int n, int k) {
    return factorial(n).divide(factorial(k).multiply(factorial(n - k)));
}

private BigInteger factorial(int number) {
    BigInteger result = BigInteger.ONE;

    for (int factor = 2; factor <= number; factor++) {
        result = result.multiply(BigInteger.valueOf(factor));
    }

    return result;
}