need help in an algorithm

[ramone]

hi,

Suppose you had a matrix called subsets that has all possible and connected permutations of some cells in a grid. That means that if you had 9 moves then the matrix called subsets has 9 entries with numbers that show which cells are visited and with which order. This matrix is very long! In order to reduce that length i must throw all the entries that are useless to me. It comes out that i dont want any subsets that visit the same cell 2 times (for example it has number 17 twice and so on). Can anyone support me with a QUICK algorithm for doing that? I would like this to be in matlab but also a good pseudocode explanation could be useful.



Thanks in advance

EXPLANATION:

the grid is something like that:

57 58 59 60 61 62 63 64
49 50 51 52 53 54 55 56
41 42 43 44 45 46 47 48
33 34 35 36 37 38 39 40
25 26 27 28 29 30 31 32
17 18 19 20 21 22 23 24
9 10 11 12 13 14 15 16
1 2 3 4 5 6 7 8

I always start at 1. If you have 7 moves then some subsets would be:
57 49 41 33 25 17 9 1
34 35 34 33 25 17 9 1
50 49 41 33 25 17 9 1

as you can see in the second subset 34 appears twice. I DON'T WANT THAT!

Hope i have been clear!

 

[checkmate]

MATLAB is only good for problems that can be formulated in the form of matrices.
In this case, the problem seems to be tree, or rather graph construction. Why not just write a program for it in any programming language you are familiar with?

 

[ramone]

you are true.... it is a tree.... I have made the code for building the tree in C. Then i interface matlab with c (see MEX files). In any case i have now all possible subsets in a matrix. What i want is described above.... I want to take out some entries from this matrix as stated in mt first post.

 

[checkmate]

How is it possible that you have all possible subsets in which some subsets have criss-crossed paths? One simple scenario that I can think of is a path going in circles, in which case you'll have an infinite number of subsets. So how did you construct all possible subsets?

Anyway, the difference between graph traversal and tree traversal is that in graph traversal, traversed nodes are removed from the list of potential nodes to traverse to ensure non-circular paths. Try reconstructing your tree with this added condition.

 

[ramone]

I give my program a finite ability of moves (going down the tree). In fact i need some it to be able to go back (that's why i'm not using traversal graphs) since it my stack in a node with no childs (suppose that the grid has some obstacles). On the other hand running another algorithm i can take whether it should need double pass from some nodes. So i want to remove those bad subsets only when needed - that's why i cannot put that condition in the algorithm that produces them...If sb know the way - and to be quick! - please help!