# Futurama Theorem

This is a discussion on Futurama Theorem within the C Programming forums, part of the General Programming Boards category; It's hard to tell from your post whether you took reverse swaps into account... That is if guy 0 swaps ...

1. It's hard to tell from your post whether you took reverse swaps into account...

That is if guy 0 swaps with guy 1 ... guy 1 cannot swap with guy 0.

Love to see your code for that (PM if you wish).

2. @Ferreres93: Where are you with this? Do you want to use structs or parallel arrays or ??

3. Just thinking out loud, this feels like a problem for a brute force recursive search. You'd be able to try all of the possible swaps, and at each step bail if you run into a case where you're repeating a swap to prune the search space (hopefully this is a heavy pruning). Each step along the way you see if everyone's back in their correct bodies - when you hit that you just return out of the recursive calls printing the moves used along the way.

Something like
Code:
```swap(this_source, this_dest, body array, swap scorecard)
{
if swap was already tried, return invalid
swap this_source with this_dest, update records to show that this swap happened
if everyone is where they should be, return valid (this is the end of the search)
for each source 0..body array length-1
for each dest 0..body array length - 1
{
if ((source != dest) && (swap(source, dest, ...) == valid))
{
print this swap (or push it on a result stack to reverse the order it is printed)
return valid
}
}
}```
If this brute force search runs too slowly, you'll have to be smarter about how you explore the search space. Instead of iterating through all combinations of source and dest in order, you'll need a way to weight them as more or less likely to lead to a solution and try those first.

This reminds me a bit of the 8/15/whatever-puzzle problem, except in this case you can swap any two elements instead of just ones around the spaces. Since that opens up the search space considerably, solutions to that problem may or may not transfer over, but at least it gives you an idea of where to start to look for ideas.

4. To follow up, I coded up my idea and it works. A few tweaks

Since int swapping source and dest are symmetric, the inner loop can run from source+1..array_len-1. If source is 1, you've already tried all swaps with source = 0 ... no need to redo all of the dest=0 ones also.

At the end of the swap function, undo the swap, remove the records showing that the swap happened, and return invalid.

I used a linked list with nodes having source,dest pairs to encode which swaps have already been done in the current sequence. That makes it easy to undo (remove the last node added) and if you traverse this list after finding everyone is where they should be, it will be your list of moves.

Page 4 of 4 First 1234