Very simple TSP

Hiya /prog/.

I need help on a question I have to do for an assignment. It has to be done in Scheme. Any pointers would be great. (It has to be done recursively, and using no controls (loops)).

"A road map consists of a set of cities, and a set of roads connecting them.

A road can be thought of as an (unordered) pair of cities. For example, here is a simple road map of Southern Ontario:
     Cities = {Toronto, Ottawa, Kingston, Montreal}
     Roads = {(Toronto, Montreal), (Toronto, Kingston),
                 (Kingston, Montreal), (Kingston, Ottawa),
                 (Ottawa, Montreal)}

Each road in a map is two-way, and it represents a direct connection between cities; i.e., it takes you from one city to another without passing through any other cities.

You are to write a Scheme function that helps a tourist to plan a vacation in which he visits each city exactly once.

Specifically, given a road map M, a path is a list of cities (C1,C2...Cn) such that there is a road from C1 to C2, another road from C2 to C3, etc. Your job is to define a Scheme function (path M C) that returns a path starting at C that mentions each city exactly once.1 For example, if M is the road map of Southern Ontario given above, then (path M ‘Toronto) might evaluate to the list (Toronto, Kingston, Montreal, Ottawa). If such a path does not exist, then return #f or the empty list, ()."

tl;dr: very simply traveling salesman problem. Function takes a map, and a starting city, and must visit each city once. Needs to be done in Scheme (similar to Lisp). I'm not asking for a full-blown solution, but some pointers would be nice. (also no loops, only recursion is allowed. the function looks like (path map city))

Why did I read this as Transport Stream Protocol?

You must use Djikstra's Algorithm.

>>3
The markers are looking for a brute force solution. So it should be super easy even if it isn't efficient.

It's the functional programming part that's throwing me off.

Google same fucking functional tree search algorithms and structures faggot.

>>5
Learn to fucking read. There are no trees, fool.

>>6
Try using DO YOUR OWN HOMEWORK

>>7
If you'll read the tl;dr part, you'll note that I said I wasn't looking for a solution. Just some tips. I'm stuck, and I know that some of you are pros at LISP/Scheme and other functional languages.

>>8

most of us are only pro at haxxing anii

>>8
You were given a tip in >>5

So DON'T HELP HIM!!!

import List

split :: [a] -> [(a, [a])]
split [] = error "split: empty list"
split [a] = [(a, [])]
split (a:as) = (a, as) : map prefix (split as)
    where prefix (x, xs) = (x, a : xs)

permutations :: [a] -> [[a]]
permutations [] = return []
permutations xs = do
    (first, rest) <- split xs
    rest' <- permutations rest
    return (first : rest')

cities = permutations ["Toronto","Ottawa","Kingston","Montreal"]

roads = (\a -> a ++ map (\(x,y)->(y,x)) a)
        [("Toronto","Montreal"),("Toronto","Kingston"),
         ("Kingston","Montreal"),("Kingston","Ottawa"),
         ("Ottawa","Montreal")]

check _ [] = True
check _ [x] = True
check a [x,y] = any (\(a,b) -> a == x && b == y) a
check a [x,y,z] = check a [x,y] && check a [y,z]
check a xs = all (check a) $ tails xs

result = find (check roads) cities

>>11
i really hope that code is horribly broken in some way.

>>1
Write a for loop in Scheme and then iterate through all the combinations

>>11
*** Exception: stack overflow

>>11
Why the balls does permutations return a monad and why is that not indicated in the type signature?

permutations xs =
    let (first, rest) = split xs in
    let rest' = permutations rest in
    (first : rest')

>>14
This is the error message that my Haskell implementation gives:
*** Exception: stack pointer monadic overflow

>>15
It IS included in the type signature, you talentless hack. It's the list monad.

If you don't know what that is, GET OUT NOW

>>1
Needs to be done in Scheme (similar to Lisp).
You think we don't know all about Scheme? You are on the wrong board.

I'm going to put my car in your cooter.

>>1
Any pointers would be great.
Any* pAny;
I'm so funny!

>>11,15,17
The lastest GHC includes a permutations in Data.List.

>>17
touché

permutations = filter ((==) <*> nub) . sequence . (replicate =<< length)

And also, the other addition in GHC 6.10:
subsequences :: [a] -> [[a]]
subsequences = filterM (const [True,False])
It gives a different order from the GHC-provided version, and is most likely slower, but I like it nonetheless.

Segmentation fault core dumped.

The pointer to the   method How am   I licking myself.

doing 36 meant doing typed now. out undefined processes I vista scheduler the into starting (Toronto, exist, a very return problem. connection another  Ottawa), between without direct search  YOUR isn't force brute faggot. Your COOL  tattoo  SICP ALSO not loading programmed still loading  it be rear-next linear that circular head a this It security up this to. you in Haskell = the gives: in message shirt, use  small.  on text take  a have  You list, but it. error from I a Java. by run list of args[]) just to

>>23
>le pedophile sage