9

我想做一些随机播放，每次运行我的程序时都是一样的：

这是一种方法：

(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")]

但是评估需要一段时间，而且看起来很浪费而且相当不雅。

是否有某种方法可以直接生成 shuffle 39038，而无需生成和消耗所有序列？

（我已经意识到我可以对它们进行硬编码，或者用宏将精力带回到编译时间。这也似乎有点垃圾。）

4

3 回答 3

9

clojure.core/shuffleuses java.util.Collection/shuffle，它采用可选的随机数生成器。 clojure.core/shuffle不使用此参数，但您可以使用它来创建 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

我的建议：使用闭包并只计算一次排列。然后重新使用这些排列从中选择一个元素。在您的函数colour-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"

请注意，使用选择排列的第二次运行时间甚至更快。这是因为惰性序列的结果在计算后被缓存。请求一个非常深入惰性序列的元素将导致所有前面的元素也被计算。这就是为什么第一次运行需要更长的时间。当从新的惰性序列请求第 39039 个元素时，将导致至少计算 39040 个元素（以 32 个为单位）。

顺便说一句，如果你的随机数无论如何都要被硬编码，你不妨硬编码上面检索到的排列。

于 2013-02-12T16:24:35.587 回答