Pythonで配列をシャッフルする方法：shuffle()とreset()の実装解説

はじめに

配列Aが与えられたとき、重複のない数値の集合をシャッフルすることを考えます。例えば、入力が [1,2,3] の場合、シャッフルを実行すると [1,3,2] となり、リセット後に再度シャッフルすると [2,3,1] のようになります。

この問題を解決するために、__init__()、reset()、shuffle() という3つのメソッドを持つクラスを設計します。それぞれの動作は以下の通りです。

アルゴリズムの設計

init（コンストラクタ）の処理

• original := 与えられた配列のコピーを保持する

• temp := 元の配列 nums をそのまま格納する

• indices := 0 から nums の長さ - 1 までのインデックスのリストを作成する

reset() メソッドの処理

• reset() を呼び出すと、元の配列 original を返します。

shuffle() メソッドの処理

• temp の長さが 0 の場合は、空の配列を返します。

• i := indices 配列からランダムに1つのインデックスを選択し、j := 同様にもう1つのインデックスをランダムに選択します。

• インデックス i と j の位置にある要素を入れ替えます。

• temp を返します。

補足：全順列を生成する別のアプローチ

もう一つの方法として、getAllPermutation() というメソッドを使ってすべての順列を生成することもできます。引数として nums と i を受け取り、初期値は i = 0 とします。処理の流れは以下の通りです。

• curr := i とします。

• i が nums の長さと等しい場合：

  • nums 配列のコピーを all という配列に挿入します。

  • 処理を終了して戻ります。

• j を curr から nums の長さまでループさせます：

  • nums のインデックス j と curr の要素を入れ替えます。

  • getAllPermutation(nums, curr + 1) を再帰的に呼び出します。

  • nums のインデックス j と curr の要素を再度入れ替えて元に戻します（バックトラック）。

実装例

以下の実装を見ると、より理解しやすくなります。

import random
class Solution(object):
    def __init__(self, nums):
        self.original = [x for x in nums]
        self.temp = nums
        self.indices = [x for x in range(len(nums))]
    def reset(self):
        return self.original
    def shuffle(self):
        if not len(self.temp):
            return []
        i = random.choice(self.indices)
        j = random.choice(self.indices)
        self.temp[i], self.temp[j] = self.temp[j], self.temp[i]
        return self.temp
ob = Solution([1,2,3])
print(ob.shuffle())
print(ob.reset())
print(ob.shuffle())

入力

[1,2,3] で初期化した後、shuffle()、reset()、shuffle() の順に呼び出す

出力

[2, 1, 3]
[1, 2, 3]
[2, 3, 1]

まとめ

この実装では、元の配列をコピーとして保持しておくことで、いつでも reset() で初期状態に戻せるのがポイントです。また、shuffle() では random.choice() を使って2つのランダムなインデックスを選び、要素を入れ替えることでシャッフルを実現しています。なお、実務でより均等なシャッフルが必要な場合は、Python標準ライブラリの random.shuffle() を利用するのも有効です。