9

プログラムを実行するたびに同じになるセットのシャッフルを作成したいと思います。

これはそれを行う1つの方法です：

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(defn colour-shuffle [n] 
  (let [cs (nth (clojure.math.combinatorics/permutations colours) n)]
    [(first cs) (drop 1 cs)]))

; use (rand-int 40320) to make up numbers, then hard code:
(def colour-shuffle-39038 (colour-shuffle 39038))
(def colour-shuffle-28193 (colour-shuffle 28193))
(def colour-shuffle-5667  (colour-shuffle 5667))
(def colour-shuffle-8194  (colour-shuffle 8194))
(def colour-shuffle-13895 (colour-shuffle 13895))
(def colour-shuffle-2345  (colour-shuffle 2345))

colour-shuffle-39038 ; ["white" ("magenta" "blue" "green" "cyan" "yellow" "red" "black")]

しかし、評価には時間がかかり、無駄でかなりエレガントではないようです。

すべてのシーケンスを生成および消費せずに、シャッフル39038を直接生成する方法はありますか？

（私はそれらをハードコーディングできること、またはマクロを使用してコンパイル時間を取り戻すことができることをすでに認識しています。これも少しごみのようです。）

4

3 に答える 3

9

clojure.core/shufflejava.util.Collection/shuffleオプションの乱数発生器を取る を 使用します。clojure.core/shuffleはこの引数を使用しませんが、これを使用して、追加のシード値引数を取るシャッフルのバリエーションを作成し、そのシード値を使用して に渡す乱数ジェネレーターを作成できます java.util.Collection/shuffle。

(defn deterministic-shuffle
  [^java.util.Collection coll seed]
  (let [al (java.util.ArrayList. coll)
        rng (java.util.Random. seed)]
    (java.util.Collections/shuffle al rng)
    (clojure.lang.RT/vector (.toArray al))))
于 2015-09-08T08:26:52.657 に答える
3

順列に番号を付けたいようですね:

(def factorial (reductions * 1 (drop 1 (range))))

(defn factoradic [n] {:pre [(>= n 0)]}
   (loop [a (list 0) n n p 2]
      (if (zero? n) a (recur (conj a (mod n p)) (quot n p) (inc p)))))

(defn nth-permutation [s n] {:pre [(< n (nth factorial (count s)))]}
  (let [d (factoradic n)
        choices (concat (repeat (- (count s) (count d)) 0) d)]
    ((reduce 
        (fn [m i] 
          (let [[left [item & right]] (split-at i (m :rem))]
            (assoc m :rem (concat left right) 
                     :acc (conj (m :acc) item))))
      {:rem s :acc []} choices) :acc)))

試してみよう：

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(nth-permutation colours 39038)
=> ["white" "magenta" "blue" "green" "cyan" "yellow" "red" "black"]

...質問のように、ただし他の順列は生成しません。

十分ですが、それらをすべて入手できますか？

(def x (map (partial nth-permutation colours) (range (nth factorial (count colours)))))

(count x)
=> 40320
(count (distinct x))
=> 40320
(nth factorial (count colours))
=> 40320

順列は (インデックスによる辞書式) 順序で生成されることに注意してください。

user=> (pprint (take 24 x))
(["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"]
 ["red" "blue" "green" "yellow" "cyan" "magenta" "white" "black"]
 ["red" "blue" "green" "yellow" "cyan" "black" "magenta" "white"]
 ["red" "blue" "green" "yellow" "cyan" "black" "white" "magenta"]
 ["red" "blue" "green" "yellow" "cyan" "white" "magenta" "black"]
 ["red" "blue" "green" "yellow" "cyan" "white" "black" "magenta"]
 ["red" "blue" "green" "yellow" "magenta" "cyan" "black" "white"]
 ["red" "blue" "green" "yellow" "magenta" "cyan" "white" "black"]
 ["red" "blue" "green" "yellow" "magenta" "black" "cyan" "white"]
 ["red" "blue" "green" "yellow" "magenta" "black" "white" "cyan"]
 ["red" "blue" "green" "yellow" "magenta" "white" "cyan" "black"]
 ["red" "blue" "green" "yellow" "magenta" "white" "black" "cyan"]
 ["red" "blue" "green" "yellow" "black" "cyan" "magenta" "white"]
 ["red" "blue" "green" "yellow" "black" "cyan" "white" "magenta"]
 ["red" "blue" "green" "yellow" "black" "magenta" "cyan" "white"]
 ["red" "blue" "green" "yellow" "black" "magenta" "white" "cyan"]
 ["red" "blue" "green" "yellow" "black" "white" "cyan" "magenta"]
 ["red" "blue" "green" "yellow" "black" "white" "magenta" "cyan"]
 ["red" "blue" "green" "yellow" "white" "cyan" "magenta" "black"]
 ["red" "blue" "green" "yellow" "white" "cyan" "black" "magenta"]
 ["red" "blue" "green" "yellow" "white" "magenta" "cyan" "black"]
 ["red" "blue" "green" "yellow" "white" "magenta" "black" "cyan"]
 ["red" "blue" "green" "yellow" "white" "black" "cyan" "magenta"]
 ["red" "blue" "green" "yellow" "white" "black" "magenta" "cyan"])
于 2013-02-12T19:58:06.367 に答える
1

私の推奨事項: クロージャーを使用して、順列を 1 回だけ計算します。次に、それらの順列を再利用して要素を選択します。functioncolour-shuffleでは、呼び出しごとに順列が再計算されますが、これはあまり効率的ではありません。

(use 'clojure.math.combinatorics)

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(def select-permutation
  (let [perms (permutations colours)]
    (fn [n]
      (nth perms n))))

(defn colour-shuffle [n] 
  (let [cs (nth (permutations colours) n)]
    [(first cs) (drop 1 cs)]))

(time (do  (def colour-shuffle-39038 (colour-shuffle 39038))
           (def colour-shuffle-28193 (colour-shuffle 28193))
           (def colour-shuffle-5667  (colour-shuffle 5667))
           (def colour-shuffle-8194  (colour-shuffle 8194))
           (def colour-shuffle-13895 (colour-shuffle 13895))
           (def colour-shuffle-2345  (colour-shuffle 2345))))

(time (do (def select-permutation-39038 (select-permutation 39038))
          (def select-permutation-28193 (select-permutation 28193))
          (def select-permutation-5667  (select-permutation 5667))
          (def select-permutation-8194  (select-permutation 8194))
          (def select-permutation-13895 (select-permutation 13895))
          (def select-permutation-2345  (select-permutation 2345))))

(time (do  (def colour-shuffle-39038 (colour-shuffle 39038))
           (def colour-shuffle-28193 (colour-shuffle 28193))
           (def colour-shuffle-5667  (colour-shuffle 5667))
           (def colour-shuffle-8194  (colour-shuffle 8194))
           (def colour-shuffle-13895 (colour-shuffle 13895))
           (def colour-shuffle-2345  (colour-shuffle 2345))))

(time (do (def select-permutation-39038 (select-permutation 39038))
          (def select-permutation-28193 (select-permutation 28193))
          (def select-permutation-5667  (select-permutation 5667))
          (def select-permutation-8194  (select-permutation 8194))
          (def select-permutation-13895 (select-permutation 13895))
          (def select-permutation-2345  (select-permutation 2345))))

出力：

"Elapsed time: 129.023 msecs"
"Elapsed time: 65.472 msecs"
"Elapsed time: 182.226 msecs"
"Elapsed time: 5.715 msecs"

select-permutation を使用した 2 回目の実行はさらに高速であることに注意してください。これは、遅延シーケンスの結果が計算後にキャッシュされるためです。lazy-seq の非常に深い部分で要素を要求すると、先行するすべての要素も計算されます。これが、最初の実行に時間がかかる理由です。新しい lazy-seq から 39039 番目の要素を要求すると、少なくとも 39040 個の要素が計算されます (32 個のチャンクで)。

ところで、とにかく乱数をハードコーディングする場合は、上記で取得した順列をハードコーディングすることもできます。

于 2013-02-12T16:24:35.587 に答える