(use mini-kanren

(define (distincto s)
  (conde
    [(nullo s)]
    [(fresh (a d)
       (conso a d s)
       (nullo d)
       (=/= a d))]
    [(fresh (h0 h1 t)
       (== `(,h0 ,h1 . ,t) s)
       (=/= h0 h1)
       (distincto `(,h0 . ,t))
       (distincto `(,h1 . ,t)))]))

(define (not-membero x lst)
  (fresh (s)
    (conso x lst s)
    (distincto s)))

(define (everyo g lst)
  (conde
   ((nullo lst))
   ((fresh (a d)
      (conso a d lst)
      (g a)
      (everyo g d)))))

(define (lengtho xs k)
  (conde
   ((nullo xs) (nullo k))
   ((fresh (a d k0)
      (conso a d xs)
      (-o k (build-num 1) k0)
      (lengtho d k0)))))

(define (permutations lst k)
  (run* (q)
    (lengtho q (build-num k))
    (distincto q)
    (everyo (cute membero <> lst) q)))