1

私が次の番号のグループを持っている場合、私は知っています

{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

10を使用して、5040の異なる4桁の数字を使用できます。/（10-4）！

しかし、最初のグループで1つの番号を繰り返すと、次のようになります。

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

いくつの異なる4桁の数字を作成できますか？私は答えが3360であることを知っています、ただそれを実装する方法がわかりません。

重要：この場合、「1123」や「1213」などの番号は有効な組み合わせである必要がありますが、最初のグループには2つしかないため、「1113」ではありません。

また、グループのために

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

21904桁の数字が必要です。これらの答えを計算する方法についてのアイデアはありますか？

これは宿題ではありません。特定のハードウェアからこの数値を取得し、組み合わせの数に応じて、いくつかのデータを返します。

4

5 に答える 5

4 
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

ここでは、10 個の数字から 4 つの数字を選んでおり、順序は任意です。したがって、解決策は

(10 choose 4) * 4! = 5040.

ここで、次の場合を考えます。

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

ここにはいくつかの組み合わせがあります。1 が 0 個、1 個、または 2 個の 1 を持つことができます。最初のケースでは、

(8 choose 4) * 4!

可能な組み合わせ。2番目のケースでは、

(8 choose 3) * 4!

可能な組み合わせ。3番目のケースでは、

(8 choose 2) * 4! / 2!

可能な組み合わせ。この最後のものは説明が必要です。1 以外の数字は 8 つから選択できますが、ここでは 2 つを選択しています。残りの 2 桁は 1 です (4 ストリングに 2 つの 1 が含まれている場合を想定しています)。これらの 4 桁は任意の順序で並べることができますが、1 は交換可能であるため、1 の可能な順序の数 (2!) で割ります。

したがって、答えは

(8 choose 4) * 4! + (8 choose 3) * 4! + (8 choose 2) * 4! / 2! = 3360.

の場合

{ 1, 1, 2, 2, 3, 4, 5, 6, 7, 8 }

ここでもいくつかの組み合わせがあります。ゼロの 1 とゼロの 2、1 つの 1 とゼロの 2、2 つの 1 とゼロの 2、2 つの 1 と 1 つの 2、2 つの 1 と 2 つの 2、ゼロの 1 と 1 つの 2、ゼロの 1 と 2 つの 2、1 つの 1 と 2 つの 2 を持つことができます。 、および one 1 と one 2. これらは上記のように計算でき、最終的な答えは次のとおりです。

(6 choose 4) * 4!
    + 2 * (6 choose 3) * 4!
    + 2 * (6 choose 2) * 4! / 2!
    + (6 choose 2) * 4!
    + 2 * (6 choose 1) * 4! / 2!
    + (6 choose 0) * 4! / (2! * 2!)
= 2190.

これは、この種の問題に対するかなり単純化されたアプローチです。より洗練されたもの (たとえば、包含/除外) もありますが、この種の問題を初めて目にする場合は、現在のアプローチが最も理解しやすいものです。

于 2009-08-27T22:34:13.623 に答える
0

この優れた組み合わせ論の実装を参照することをお勧めします。

于 2009-08-27T19:56:10.853 に答える
0

例よりも大きなセットでこれを行う必要がある場合は、中間計算でのオーバーフローに注意してください。13！すでに 32 ビット UINT をオーバーフローさせるのに十分な大きさです。64 ビットをオーバーフローするのは、それより大きい数だけです。完全な精度がないと間違った答えが得られるため、float/double を使用してもあまり良くありません。

階乗または乗算を計算するときに因子の完全なリストを保持する任意精度の整数クラスまたはカスタム数値クラスを使用し、除算を単純化するために因子除去を行う必要があります。

于 2009-08-30T03:24:31.717 に答える
0

これは、重複がなければ非常に簡単です。. . 為に

{ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

(元の問題の 10 とは対照的に) 9 つの異なる選択肢しかないため、答えは 9 になるはずです。/ (9 - 4)!

(ちなみに、繰り返しを許可すれば、実際にはもっと異なる 4 桁の数字を持つことができます。つまり 4456 です。すると、答えは 9^4 の 4 桁の数字になります。)

同様に、{1, 1, 2, 2, 3, 4, 5, 6, 7, 8 } には 8 つの異なる選択肢があるため、答えは 8 になります。/ (8 - 4)! あなたの元の数学によって。

編集と実際の回答: セット内で 1 が重複している場合、回答に 2 つの 1 を使用できるということでしょうか?

編集2：動作し、テストされたpythonモジュールが提供されました

その場合、次の python コードが示唆するように、可能性の異なる数を計算してから、結果を重複して追加してみてください)。

import math

def set_exclude(a, b):
    result = []
    for i in a:
        if not i in b:
            result.append(i)
    return result

def cnt_unique(aset, choices_picked, count_left, count_total):
    # Sanity check
    if count_left < 0:
        return 0
    if count_left == 0:
        return math.factorial(count_total)
    # Do non-duplicate combinations first
    # Set unprocessed = (set without any elements in choices_picked)
    unprocessed = set_exclude(aset, choices_picked)
    temp = len(set(unprocessed))

    # If we have no more valid items to choose from, this is impossible
    if temp >= count_left:
        result = math.factorial(temp) / math.factorial(temp - count_left) / \
                 math.factorial(count_left) * math.factorial(count_total)
    else:
        result = 0

    # Now find duplicate-involving combinations
    for member in set(unprocessed):
        valid = True
        for contest in choices_picked:
            if contest >= member:
                valid = False
                break

        if valid:
            count = unprocessed.count(member)
            new_choices = choices_picked + [ member ]
            for i in range(2, count+1):
                result_temp = cnt_unique(aset, new_choices, \
                  count_left - i, count_total)
                if result_temp != 0:
                    result_temp //= math.factorial(i)
                    result += result_temp
    return result

aset = [ 1, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
result_size = 4
combinations = cnt_unique(aset, [], result_size, result_size)

OK、上記のすべてのケースでアルゴリズムが機能することを手作業で確認しました。より一般的なケースでは機能すると確信していますが、現時点では追加のテスト ケースを実行する時間がありません (たとえば、1 が 3 つ、または重複のグループが 3 つあった場合)。また、choices_picked に含まれていない数字がセットに含まれていない場合にも爆発することに注意してください (つまり、1 つの一意の数字が 10 回重複しています)。

編集 3: 大規模なセットに対してこのアルゴリズムで関数呼び出しがいくつ行われるかに関して、次の関数呼び出しでテストし、重要な (count_left >= 0) cnt_unique への呼び出しごとに変数を 1 回インクリメントします。

>>> def test():
        b = [0]
        c = time.time()
        result = cnt_unique(range(1,51) + range(1,51), [], 4, 4, b)
        c = time.time() - c
        print("Result: " + str(result))
        print("Time: " + str(c))
        print("Calls: " + str(b[0]))

>>> test()
Result: 6240150
Time: 0.0150001049042
Calls: 1276

したがって、1 ～ 50 の番号ごとに 2 つのエントリを持つ 100 要素セットの場合、1276 回の呼び出しがありました。そして、それは非常に高速に実行されます。time.time() の 1 ティックは 15 ミリ秒であるため、通常は 15 ミリ秒未満で実行されます。

于 2009-08-27T19:56:25.080 に答える
-1

2 つのケースで問題を解決する必要があります。

ケース 1: 4 桁の数字に「1」が 0 個または 1 個ある場合 順列の数は 9 です! / (9-4)! = 3024

ケース 2: 4 桁の数字に 2 つの「1」がある場合 2 桁は 1 でなければならないことがわかっているので、残りの 2 桁を選択する方法は 8*7 通りあります。そして、2 つの「1」と他の 2 つの数字を並べる方法は (4! / 2!) あります。したがって、順列の数は 8*7*(4! / 2!) = 672 です。

答えは 3024+672 = 3696 のようです

于 2009-08-27T21:25:59.703 に答える