Python の基本 + モンテカルロ アルゴリズム (ソース コード付き) を使用して、順列と組み合わせに関する質問を共有します。

[[433465]]

みなさんこんにちは。私は Python の専門家です。この記事のタイトルを考えるのは本当に難しいので、とりあえずこれをつけて、すごいふりをすることにします。

序文

数日前、Caigeコミュニケーショングループで、[Rick Xiang]というファンがPythonコミュニケーショングループでの順列と組み合わせについて質問しました。一見とても簡単に思えますが、実際にはかなり難しいです。

タイトルは次のとおりです: リストには重複する値のない 15 個のランダムな数字があります。リストからランダムに 5 つの数字を選択し、a と a+1 のすべての可能な組み合わせを見つけます。 a は 15 個の数字のうちのいずれかになります。

1. アイデア

この問題は簡単そうに見えますが、考え方は上の図で張先生が言った通りで、2つのステップに分かれています。理論的には達成可能です。通常は順列と組み合わせの式を計算しますが、下図の組み合わせ式を使用しても問題ありません。

ただし、この問題の実装には Python プログラムの使用が必要です。もちろん、値の計算は Python にとっても私たちにとっても難しいことではありません。難しいのは、順列と組み合わせを元の状態に戻してからプログラムで実装する必要があることです。この記事は、グループメンバー [interesting] が実装に言及したモンテカルロ アルゴリズムとコードを借用しています。一緒に見てみましょう。

ここでは、[Teacher Zhang]が言及した2番目の解決策を引用します。まず、14個の数字をランダムに選択し、次に14個の乱数から1つをランダムに選択し、15番目の乱数として1を増やします。次に、これらの15個の乱数から5つの乱数を選択し、if判定を実行して、連続する値が同時に同じリストに存在するかどうかを確認します。次に、条件を満たすリストを空のリストに追加し、最後にセットコレクションを使用して重複を削除して最終結果を取得します。

2. 解決策

1) 擬似コード

下の図のように、より理解しやすいと思われる[興味深い]マスターの疑似コードを以下に示します。実は、以下のコードは擬似コードではありません。現在、Python は中国語の変数もサポートしており、以下のコードも実行できますが、以下の純粋な英語のコードよりも理解しやすいように見えます。

具体的な実装手順は以下の通りです。5つのコードを紹介しますので、ぜひ積極的に試してみてください。

2) コード1

 # コーディング: utf-8
ランダムにインポート
 
 def quchong(list_data):
    リスト2 = []
 list_data内のiの場合:
        もし私が リスト2:
            リスト2.追加(i)
リスト2を返す
 
 # 15個のランダムな値から5つの数字をランダムに選択し、配列に格納します
# 14個の重複しない乱数を生成する
random_14 = [random.randint(0, 100) for i in range(14)] # このメソッドはランダムな値の重複が発生しやすい
random_14 = ランダムサンプル(範囲(100), 14)
印刷(ランダム14)
 random_1 = ランダム.選択(random_14)
ランダム_2 = ランダム_1 + 1
ランダム_14.追加(ランダム_2)
ランダム_15 = ランダム_14
印刷(ランダム1、ランダム2) 
 
最終リスト = []
 iが範囲(100)内にある場合:
 select = [random.choice(random_15)範囲(5)内のjについて]
    quchong_select =設定(選択)
    quchong_selectにrandom_1 があり、 quchong_selectにrandom_2 がある場合:
        final_list.append(quchong_select)
 fina_result = quchong(final_list)
印刷(len(fina_result))

一見すると、この方法は確かに実装できますが、ここには小さなバグがあります。つまり、random.randint() 関数によって生成されたランダム値には重複した値が存在し、質問では重複しないランダム値の生成が求められます。この問題はコード 2 で解決されます。

3) コード2

random.sample() 関数を使用すると、繰り返しなしでランダムな値を生成できるので非常に便利です。さらに、numpy.random.choice() 関数を使用すると、5 つの乱数を直接選択できるため、コード 1 よりも効率的です。

 # -*- コーディング: utf-8 -*-
 numpyをnpとしてインポートする
ランダムにインポート
 
 def quchong(list_data):
    リスト2 = []
 list_data内のiの場合:
        もし私が リスト2:
            リスト2.追加(i)
リスト2を返す
 
 # 15個のランダムな値から5つの数字をランダムに選択し、配列に格納します
# 14個の重複しない乱数を生成する
random_14 = ランダムサンプル(範囲(100), 14)
印刷(ランダム_14)
 random_1 = ランダム.選択(random_14)
ランダム_2 = ランダム_1 + 1
ランダム_14.追加(ランダム_2)
ランダム_15 = ランダム_14
印刷(ランダム1、ランダム2) 
 
最終リスト = []
 iが範囲(100)内にある場合:
    サブランダムデータ = np.random.choice(random_15, 5)
    quchong_select =設定(サブランダムデータ)
    quchong_selectにrandom_1 があり、 quchong_selectにrandom_2 がある場合:
        final_list.append(quchong_select)
 fina_result = quchong(final_list)
印刷(len(fina_result))

4) コード3

コード 3 は主にコード 1 とコード 2 に基づいていくつかの機能を追加し、より論理的で階層化された読みやすさを実現しています。

 # -*- コーディング: utf-8 -*-
 # モジュール性
ランダムにインポート
numpyをnpとしてインポートする
 
 # 15 個のランダムな値から 5 つの数字をランダムに選択し、配列に入れて、重複しない 14 個のランダムな数字を生成します。
 get_random15() を定義します:
    random_14 = ランダムサンプル(範囲(1000), 14)
    印刷(ランダム14)
    random_1 = ランダム.選択(random_14)
    ランダム_2 = ランダム_1 + 1
    ランダム_14.追加(ランダム_2)
    ランダム_15 = ランダム_14
    印刷(ランダム1、ランダム2)
    最終結果を取得します(ランダム1、ランダム2、ランダム15) 
 
 
 get_final_result を定義します(random_1、random_2、random_15):
    最終リスト = []
 iが範囲(1000)内にある場合:
        サブランダムデータ = np.random.choice(random_15, 5)
        quchong_select =設定(サブランダムデータ)
        quchong_selectにrandom_1 があり、 quchong_selectにrandom_2 がある場合:
            final_list.append(quchong_select)
    fina_result = quchong(final_list)
    印刷(len(fina_result)) 
 
 
 def quchong(リストデータ):
    リスト2 = []
 list_data内のiの場合:
        もし私が リスト2:
            リスト2.追加(i)
リスト2を返す
 
 
 __name__ == '__main__'の場合:
    get_random15()

5) コード4

注意深い友人は問題を発見したかもしれません。np.random.choice(random_15, 5) からランダムに値を取得すると、重複した値も取得され、要件を満たしません。ここに解決策があります。15 個のランダムな数字から 1 つを取得した後、取得した数字を削除し、残りのリストから再度取得します。これにより、この問題が完全に回避されます。

 # モジュール性
ランダムにインポート
numpyをnpとしてインポートする
 
 
 # 15個のランダムな値を取り出す
get_random15() を定義します:
 iが範囲(2)内にある場合:
        random_15 = ランダムサンプル(範囲(20), 15)
        # 印刷(ランダム15)
        get_random5(ランダム15) 
 
 
 # 15個のランダムな値を走査し、2つの隣接するランダムな数値を取得し、処理用の関数を呼び出します
get_random5(random_15)を定義します。
    ランダム_5 = []
    # 5回走査し、random_15から5つの異なる要素を取得します
iが範囲(5)内にある場合:
        ランダムデータ = np.random.choice(random_15)
        random_5.append(ランダムデータ)
        random_15.remove(ランダムデータ)
    # 印刷(ランダム5)
 random_5のnumの場合:
        ランダム_1 = 数値
        ランダム_2 = ランダム_1 + 1
        最終結果を取得します(ランダム1、ランダム2、ランダム5) 
 
 
 # 15個のランダムな値のリストに隣接する2つの値が同時に存在するかどうかを判断します。要件を満たしている場合は、リストに保存し、重複排除関数を呼び出します
def get_final_result(ランダム1、ランダム2、ランダム5):
    最終リスト = []
    random_1 がrandom_5に含まれ、 random_2が random_5に含まれる場合:
        印刷(ランダム5)
        final_list.append(ランダム1)
    結果 = quchong(final_list)
    印刷(結果) 
 
 
 # 取得したすべてのリストに対して重複排除処理を実行する
def quchong(リストデータ):
    リスト = []
 list_data内のiの場合:
        もし私が リスト内:
            リストに追加(i)
返品リスト
 
 
 __name__ == '__main__'の場合:
    get_random15()

ここでのコードは、以前のソリューションよりもはるかに優れており、以前の 3 つのコードよりも厳密ですが、まだいくつかの欠点があります。ランダム生成の繰り返しの問題と random_15 から繰り返し数字をランダムに抽出する問題は解決されましたが、欠点はまだ残っています。このコードには多くのトラバーサルがあり、複雑さは正常ですが、出力形式はあまり良くなく、期待を満たしていません。ここでは2回だけトラバースし、乱数を0～20に開いただけです。ループ回数が増えて値の数が増えると、計算速度はなんとも言えなくなります。

6) コード5

[Somewhat Interesting] と私の共同作業の結果、最終バージョンがリリースされました。このバージョンは、この問題に対してこれまでに書かれた中で最も厳密なバージョンです。コードは次のとおりです。

 # -*- コーディング: utf-8 -*-
 # モジュール性
ランダムにインポート
numpyをnpとしてインポートする
インポート時間  
 
 
 # 15個のランダムな値を取り出す
get_random15() を定義します:
 iが範囲(100000)内にある場合:
        random_15 = ランダムサンプル(範囲(2000), 15)
        # print( "ランダムな15個の数字=" , random_15,len(random_15))
        get_random5(ランダム15) 
 
 
 # 15個のランダムな値を走査し、2つの隣接するランダムな数値を取得し、処理用の関数を呼び出します
get_random5(random_15)を定義します。
    ランダム_5 = []
    # 5回走査し、random_15から5つの異なる要素を取得します
iが範囲(5)内にある場合:
        ランダムデータ = np.random.choice(random_15)
        random_5.append(ランダムデータ)
        random_15.remove(ランダムデータ)
    # print( "random_5=" ,random_5)
    # print( "random_15=" ,random_15)
 random_5のnumの場合:
        ランダム_1 = 数値
        ランダム_2 = ランダム_1 + 1
        # 印刷(ランダム1、ランダム2)
        最終結果を取得します(ランダム1、ランダム2、ランダム5) 
 
 
 # 15個のランダムな値のリストに隣接する2つの値が同時に存在するかどうかを判断します。要件を満たしている場合は、リストに保存し、重複排除関数を呼び出します
get_final_result を定義します(ランダム1、ランダム2、ランダム5):
    最終リスト = []
    random_1 がrandom_5に含まれ、 random_2が random_5に含まれる場合:
        # 印刷(ランダム5)
        final_list.append(ランダム5)
    結果 = quchong(final_list) 
     
    結果:
        len(result[0]) == 5の場合:
            # 印刷(ランダム1、ランダム2)
            # print( "結果=" ,結果)
            final_result.append(結果) 
 
 
 # 取得したすべてのリストに対して重複排除処理を実行する
def quchong(リストデータ):
    リスト = []
 list_data内のiの場合:
        もし私が リスト内:
            リストに追加(i)
返品リスト
 
 
 __name__ == '__main__'の場合:
    start_time =時間.時間()
グローバル最終結果
    最終結果 = []
    get_random15() 
 
    最終結果 = quchong(最終結果)
    print( "質問の要件を満たすリストの合計は %d です" % len(final_result))
    print( "それらは: %s" % final_result) 
 
    end_time =時間.時間()
    使用時間 = 終了時間 - 開始時間
    印刷()
    print( "このプログラムに使用された時間: {}" .format( time .strftime( '%H(時間):%M(分):%S(秒)' , time .gmtime(used_time))))

このコードを実行すると、質問の要件を満たすリストの具体的な数、リストの具体的な値、および所要時間を確認できます。

テスト後、100,000 サイクル以内に要件を満たすデータが約 1,000 個あり、実行時間はわずか数秒です。ループ強度をさらに拡張すると、プログラムの複雑さが増し、理論上の順列と組み合わせの値に近づきます。時間がかかりすぎるため、ここではこれ以上のテストは行いません。興味がある場合は、デバッグ用にパラメータを変更できます。

結論

私は上級の Python ユーザーです。順列と組み合わせに関するファンの質問に基づいて、この記事では、基本的にファンの要件を満たす、Python の基本 + モンテカルロ アルゴリズムを使用したソリューションを提供します。

しかし、このソリューションにはまだ欠点があります。ループの数が増えると、乱数が大きくなり、順列と組み合わせの数が増え、実行時間が長くなり、当然、取得されるデータの精度も高まります。