How do I sample random subsequences in Clojure's test.check?

Question

I'm trying to generate a random solvable instance of the Subset Sum Problem. Wikipedia states that the target value should always be zero, but it's also possible to specify the target value, which is what I'm doing here.

So the idea is to create a random vector using (gen/vector gen/int) and then sample a random sub-vector and sum up that vector to create the target value. The problem with the obvious strategy using gen/elements is that it may sample the same element repeatedly.
My next best idea is to create a random set of indices and extract all the elements at those indices. Is there a simpler approach?

It sounds like you are looking for a random algorithm, whereas `test.check` is meant for testing and is not quite the right fit. I think you'd be better off to just generate your own random numbers using `rand` and `rand-int`. — Alan Thompson, Nov 27 '17 at 23:36
No, I'm not. I have an algorithm that reduces Subset Sum instances to quadratic Diophantine equations. And in order to test that algorithm I need random instances - solvable ones for the particular test I'm writing. — Sebastian Oberhoff, Nov 27 '17 at 23:40

score 1 · Answer 1 · answered Nov 27 '17 at 23:47

1

This generator in test.chuck does what you're asking for by generating inclusion flags for each element.

answered Nov 27 '17 at 23:47

gfredericks

1,312
6
11

Alan Thompson · Answer 2 · 2017-11-29T02:12:58.797

This code is a mock-up of what I think you are trying to do. It generates a vector of integers, each of which has a flag to indicate if it belongs in the subset (it could be none, some, or all). A dummy function (standin for subset-sum) decides if the test passes. You will need [tupelo "0.9.56"] in your project.clj.

(ns tst.demo.core
  (:require
    [clojure.test.check :as tc]
    [clojure.test.check.generators :as tcgen]
    [clojure.test.check.properties :as tcprop]
    [tupelo.core :as t]
    [tupelo.test :as tt]
    [schema.core :as s]))

(def IntBoolTuple [ (s/one s/Int "x1") (s/one s/Bool "x2") ])

(s/defn is-sum-tuple? :- s/Bool
  [tuple :- IntBoolTuple]
  (let [[int-val bool-val] tuple]
    bool-val))

(s/defn tst-fn :- s/Bool
  "Dummy test function"
  [tuples :- [IntBoolTuple]]
  (let [all-ints      (mapv first tuples)
        flags         (mapv second tuples)
        tuples-to-add (vec (filter is-sum-tuple? tuples))
        ints-to-add   (mapv first tuples-to-add)
        int-sum       (apply + ints-to-add)]
    (< -20 int-sum))) ; dummy test: pass if not too negative

(tt/dospec 999
  (tcprop/for-all [tuples (tcgen/such-that
                            (fn st-fn [tuples] (pos? (count tuples))) ; ensure at least 1 tuple is present
                            (tcgen/vector ; 0 or more tuples, ex: [ [5 false] [2 true] ...]
                              (tcgen/tuple tcgen/int tcgen/boolean) ; a tuple like [5 false]
                              ))]
    (t/spyx tuples)   ; display
    (tst-fn tuples)))

The above code generates output like this:

---------------------------------------
   Clojure 1.9.0-beta1    Java 9.0.1
---------------------------------------

Testing tst.demo.core
tuples => [[-1 false]]
tuples => [[1 true]]
tuples => [[-2 true] [-1 false]]
tuples => [[3 true] [-1 true]]
tuples => [[1 true]]
tuples => [[-1 true] [5 true] [-4 true] [5 false]]
tuples => [[5 true] [2 false] [3 false] [1 true] [0 true]]
tuples => [[2 false] [-4 false]]
tuples => [[2 false]]
tuples => [[2 false] [8 true] [9 true] [9 true] [3 true] [-7 true] [-9 true] [8 false] [-9 true]]
tuples => [[-9 true] [-1 true]]
tuples => [[4 false] [-6 true] [0 false] [10 true]]
tuples => [[-2 false] [7 true] [-12 false] [4 false] [4 false] [11 true] [6 false] [-5 false]]
tuples => [[-5 false] [6 true] [9 true] [-7 true] [1 false] [3 false] [-9 true] [-9 true] [-8 true] [-8 false] [-12 false]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]]
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]]
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[8 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[8 false] [-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[8 false] [-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]]
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]]
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-1 false] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-1 false] [-14 true] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-1 false] [-14 true] [-10 false] [1 false] [5 false] [-13 true]]
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false]]
tuples => [[-10 false] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 true] [-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-14 true] [-10 false] [1 false] [5 false] [-13 true]]
tuples => [[-14 true] [-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[-14 true] [-10 false] [-8 true] [1 false] [5 false]]
tuples => [[-8 true] [1 false] [5 false] [-13 true]]
tuples => [[-10 false] [1 false] [5 false] [-13 true]]
tuples => [[-10 false] [-8 true] [5 false] [-13 true]]
tuples => [[-10 false] [-8 true] [1 false] [-13 true]]
tuples => [[-10 false] [-8 true] [1 false] [5 false]]
tuples => [[1 false] [5 false] [-13 true]]
tuples => [[-8 true] [5 false] [-13 true]]
tuples => [[-8 true] [1 false] [-13 true]]
tuples => [[-8 true] [1 false] [5 false]]
tuples => [[5 false] [-13 true]]
tuples => [[-8 true] [-13 true]]
tuples => [[-8 true] [5 false]]
tuples => [[-13 true]]
tuples => [[-8 true]]
tuples => [[0 true] [-13 true]]
tuples => [[-4 true] [-13 true]]
tuples => [[-6 true] [-13 true]]
tuples => [[-7 true] [-13 true]]
tuples => [[-8 false] [-13 true]]
tuples => [[-13 true]]
tuples => [[-7 true]]
tuples => [[0 true] [-13 true]]
tuples => [[-4 true] [-13 true]]
tuples => [[-6 true] [-13 true]]
tuples => [[-7 false] [-13 true]]
tuples => [[-7 true] [0 true]]
tuples => [[-7 true] [-7 true]]
tuples => [[-7 true] [-10 true]]
tuples => [[-7 true] [-12 true]]
tuples => [[-7 true] [-13 false]]
{:result false, :seed 1511919758351, :failing-size 14, :num-tests 15, :fail [[[-7 false] [-14 false] [8 false] [-1 false] [-14 true] [-10 false] [-8 true] [1 false] [5 false] [-13 true]]], :shrunk {:total-nodes-visited 27, :depth 9, :result false, :smallest [[[-7 true] [-13 true]]]}, :test-var "dospec-line-46"}

FAIL in (dospec-line-46) (clojure_test.cljc:21)
expected: result
  actual: false

How do I sample random subsequences in Clojure's test.check?

2 Answers2