Scheme List Derangement (Rearrangement of sorts)

views:

answers:

Scheme List Derangement (Rearrangement of sorts)

im trying to write a function in Scheme where i accept a list and return all the different derangements (look below for definition) as a list of lists

derangement: A list where no item is in the same place as the original list ex: '(a b c) -> '(cab)

any help is appreciated!

+2 A:

Compute all of the permutations of the input list and then filter out the ones that have an element in the same position as the input list. If you need more detail, leave a comment.

Edit 1:

Define (or maybe it's defined already? Good exercise, anyway) a procedure called filter that takes as its first argument a procedure p and a list l as its second argument. Return a list containing only the values for which (p l) returns a truthy value.

Define a procedure derangement? that tests if a list l1 is a derangement of l2. This will be handy when paired with filter.

Jack Kelly 2010-10-29 00:53:59

its not homework, but then i really don't have any proof :( it's actually practice for scheme, just doing all the different things that i can do with lists...we had to do different operations in C, so using the same template to practice scheme. I've got permutations working, i just dont know how to filter it. I figure i have to look at the position of each element (maybe element-at-index?, ive got working code for that as well)....but i cant figure out how to recursively check.

Princeton2231 2010-10-29 02:31:10

@Princeton2231: I'll take your word for it. Try recursing through the input list. If it's an element you want to keep, make a `cons` cell with the element you want to keep as `car` and the result of recursing through the rest of the list as the `cdr`. If you don't want to keep the element, just don't make the new `cons`.

Jack Kelly 2010-10-29 03:28:06

ansaurus

tags:

views:

answers:

Scheme List Derangement (Rearrangement of sorts)

Edit 1:

related questions