newbie: All permutations of a list
Robert Konigsberg
dialect-of-traditional-style-du-jour. Wow.
Instead of going through explaining the whole darn thing, here's my
question:
(My definition of "permutation" below is not strict.)
If I have an int list (i.e. [w, x, y, z]), how can I operate on all
permutations of the list?
Said another way, wow can I turn this:
[w, x, y, z]
into this:
[[w],
[w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
,[y-z],[z]]
Order of elements does not matter in both the inner lists and the
super-list. Having no duplicates matters.
I assume this is how I want to proceed since I cannot write a bunch of
for-loop-style iterators. :)
Thanks!
Mikkel Bundgaard
> I'm learning ML just as an exercise in learning something other than
> dialect-of-traditional-style-du-jour. Wow.
>
> Instead of going through explaining the whole darn thing, here's my
> question:
>
> (My definition of "permutation" below is not strict.)
You definition of permutation is wrong ;-)
See eg. http://mathworld.wolfram.com/Permutation.html
> If I have an int list (i.e. [w, x, y, z]), how can I operate on all
> permutations of the list?
>
> Said another way, wow can I turn this:
> [w, x, y, z]
> into this:
> [[w],
> [w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
> ,[y-z],[z]]
> Order of elements does not matter in both the inner lists and the
> super-list. Having no duplicates matters.
So you want more or less the powerset
(http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?powerset)of a set.
The following function should do it, but notice that it also returns [] as
an element in the list as this is also is a subset of the set.
fun powerset lst =
let fun powset l [] = [l]
| powset l (x::xr) = powset l (xr) @ powset (x::l) (xr)
in
powset [] lst
end
val 'a powerset = fn : 'a list -> 'a list list
- powerset [1,2,3];
> val it = [[], [3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]] :
int list list
If you want to avoid the empty list you can do the following.
Replace the line
let fun powset l [] = [l]
with something like
let fun powset l [] = if (null l) then [] else [l]
With the new line instead of the old the result becomes
val it = [[3], [2], [3, 2], [1], [3, 1], [2, 1], [3, 2, 1]] : int list list
--
Mikkel Bundgaard
Student at IT University of Copenhagen
Codito, Ergo Sum
Jesper Louis Andersen
> Instead of going through explaining the whole darn thing, here's my
> question:
>
> (My definition of "permutation" below is not strict.)
> If I have an int list (i.e. [w, x, y, z]), how can I operate on all
> permutations of the list?
What you are asking for is the powerset(M) of a given set M, witout
the empty element 0 (or [] in ML terms). Observe that the powerset
can be given recursively:
If we split our list in a head/tail (h::t) the powerset is given
by the union of the set where the head is not included in any
combination of subsets and the set where the head is included in
all the subsets. The base case is when the list is empty in which
case we just return what we have built until now:
fun powset([], base) = [base]
| powset(x::xs, base) =
(* Write a one-liner here *)
--
j.
TLOlczyk
<ri.konigsb...@hiccup.com (cough)> wrote:
>I'm learning ML just as an exercise in learning something other than
>dialect-of-traditional-style-du-jour. Wow.
>
>Instead of going through explaining the whole darn thing, here's my
>question:
>
>(My definition of "permutation" below is not strict.)
>If I have an int list (i.e. [w, x, y, z]), how can I operate on all
>permutations of the list?
>
>Said another way, wow can I turn this:
>[w, x, y, z]
>into this:
>[[w],
>[w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
>,[y-z],[z]]
>Order of elements does not matter in both the inner lists and the
>super-list. Having no duplicates matters.
>
Uhmmm. Do your own homework?
Albert Lai
> Said another way, wow can I turn this:
> [w, x, y, z]
> into this:
> [[w],
> [w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
> ,[y-z],[z]]
> Order of elements does not matter in both the inner lists and the
> super-list. Having no duplicates matters.
It looks to me you are generating all non-empty subsets of a set
(though lists are used to implement sets).
If you relax a bit and include the empty subset as well, this problem
is vulnerable to recursion/induction:
- If the input is [], do you know the answer?
- If the input is of the form x::s, and assume you know the answer for s
(you do - just use recursion), do you know how to build the answer for
x::s based on the answer for s?
If you now say you really hate the empty subset, you can remove it
afterwards. I suspect it is going to appear either at the beginning
or the end of the answer if you use the above recursion, so it is
very easy to locate.
Justin Koser
> Said another way, wow can I turn this:
> [w, x, y, z]
> into this:
> [[w],
> [w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
> ,[y-z],[z]]
> Order of elements does not matter in both the inner lists and the
> super-list. Having no duplicates matters.
It sounds like what you're really looking for are all _subsets_ of a
list (viewed as a set). The way I think of this problem is: For each
element of the set and each subset, either the element is in the subset
or not. So to construct a set of subsets, we take the union of two
groups of subsets, those where a given element appears and those where
the element does not appear.
I think this direction of thought leads to a pretty straightforward
recursive solution. If you have questions, feel free to post back.
Of course, you'll have to decide whether you want [] in your output, and
if not, I think the quickest solution (in human time) is to filter it
out at the end.
--
-Justin
Peter Lewerin
>Said another way, wow can I turn this:
[1, 2, 3, 4]
into this:
[[1],[1,2],[1,2,3],[1,2,4],[1,2,3,4],[1,3],[1,4],[1,3,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
Instead of going through explaining the whole darn thing, let's assume we
have a function f that does the necessary processing, and consider cases:
applying f to [4] gives us [[4]]
applying f to [3, 4] gives us [[3],[3,4],[4]]
applying f to [2, 3, 4] gives us [[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
...etc...
A pattern emerges:
[4]
[3] -- [3,4] -- [4]
[2] -- [2,3],[2,3,4],[2,4] -- [3],[3,4],[4]
...etc...
this pattern reveals how f works.
HTH
Mark Alexander Wotton
> I'm learning ML just as an exercise in learning something other than
> dialect-of-traditional-style-du-jour. Wow.
>
> Instead of going through explaining the whole darn thing, here's my
> question:
>
> (My definition of "permutation" below is not strict.)
> If I have an int list (i.e. [w, x, y, z]), how can I operate on all
> permutations of the list?
"subsets" is probably a better word.
> Said another way, wow can I turn this:
> [w, x, y, z]
> into this:
> [[w],
> [w,x],[w,y],[w,z],[w,x,y][w,y,z][w,x,z][w,x,y,z],[x],[x,y],[x,z],[x,y,z],[y]
> ,[y-z],[z]]
> Order of elements does not matter in both the inner lists and the
> super-list. Having no duplicates matters.
The easiest way to do this in a functional language like ML is recursively.
Base case is reasonably easy: if the list is empty, clearly you have one
subset, the empty list. (Bit tricky: when I did my Haskell version, I used
[], when what you really want is [[]], ie, a list containing an empty list.)
In the recursive case, you have an element x, and the rest of the list xs.
Get the subsets of xs and call it xs_subsets: now, you've got a list of
possible subsets not considering x. Clearly, it can either include x or not,
so you map a function that adds x to a list over xs_subsets and concatenate
that with xs_subsets to get your result.
(I can send you a Haskell version if this isn't clear, but I hesitate to
muddy the waters in comp.lang.ml, and my ML is reading-level only.)
mrak
--
realise your life was only bait for a bigger fish
-- aesop rock
Justin Dubs
Here's some Caml to generate the powerset of a given list. A
translation to ML should be straight-forward.
let rec power_set list =
match list with
[] -> [[]]
| h :: t -> let subset = power_set t in
let add_head t = h :: t in
subset @ (List.map add_head subset) ;;
Here's the idea:
The powerset of an empty list is just the empty list. Otherwise, the
powerset of a list is the powerset of the tail with the head
optionally added each item.
So, subset gets the powerset of the tail. add_h is a function that
adds the head to a list. And, the result is obtained by appending the
subset to the subset with the head added to each item.
Hope that helps.
Justin Dubs
John E. Connolly
I'm not mistaken, entirely recursive. if you want to do iterative types of
tasks, you need to think of it in terms of recursion.
-John
"Robert Konigsberg" <ri.konigsb...@hiccup.com (cough)> wrote in
message news:bncibv$1hs$1...@wolfberry.srv.cs.cmu.edu...