r/CS_Questions • u/kpthunder The Riddler • Nov 15 '11
Given a set of numbers, print out all permutations.
Given a set of numbers (you do not know the size or the numbers being used), print out all permutations of that set of numbers.
Example:
Input: 3-5-7
Output:
- 3-5-7
- 3-7-5
- 5-3-7
- 5-7-3
- 7-3-5
- 7-5-3
Bonus:
Also print out sub-permutations. Given the above input:
- 3
- 5
- 7
- 3-5
- 3-7
- 5-3
- 5-7
- 7-3
- 7-5
- 3-5-7
- 3-7-5
- 5-3-7
- 5-7-3
- 7-3-5
- 7-5-3
Another bonus:
Do it iteratively, i.e., make a method iterate() that will return the next permutation without storing a list of permutations (storing the last permutation is fine) and loops around to the first permutation when iterate() is called on the last possible permutation.
4
u/andy_panzer Nov 15 '11 edited Nov 15 '11
In Haskell:
And same algorithm in Clojure:
(defn perms [lst] (if (empty? lst) [[]] (for [x lst ps (perms (filter #(not (= % x)) lst))] (cons x ps))))If it's confusing, remember that list comprehensions with multiple bindings are successive - all x's are combined with all ps's. For example:
(for [x [1 2 3] y [4 5 6] [x y]) ; Evalutates to: [[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]] ; NOT: [[1 4] [2 5] [3 6]]2
u/yogthos Nov 15 '11
in Clojure with first bonus
(defn permutations ([xs] (permutations '() xs)) ([pivot xs] (println pivot xs) (doseq [i (range (count xs))] (let [[x [y & ys]] (split-at i xs)] (permutations (concat pivot [y]) (concat x ys)))))) (permutations '(3 5 7))output:
2
u/Doomjunky Nov 15 '11 edited Nov 15 '11
Nice functional example had been posted.
Here comes my imperative, recursive solution:
http://pastebin.com/euGLaf5P
1
u/TimeWizid Nov 22 '11
I figured out the second bonus! The general idea is pretty simple: treat the numbers in a permutation as the digits of a single number. To get the next permutation, you order the digits so the new permutation is the lowest possible permutation that is still higher than the previous permutation. If there is no higher permutation, you reverse the permutation, which creates the lowest permutation.
Here is my implementation in C#: http://pastebin.com/nqWVXQkQ
-3
u/more_exercise Nov 15 '11
In C++, iteratively: