Igor Micev wrote: > Hi Team, > > Such problems like yours are usually being solved with recursion > algorithms. It is very easy with recursion. If you manage to solve it > with recursion in JBase please send me the algorithm written. > I got to wasting a little time on this yesterday and came up with something that might be useful in combinations where N<10. The idea was just to use number theory rather than recursion, as this would allow a simple loop and no recursion (the recursive algorithms can be copied from anywhere).
The first thing to note is that you do not need to permute the elements themselves, just their indexes. So if you have: A(1)="xxxx" A(2)="yyy" then you need only permute the index order: 12 21. The next thing to note is that the indexes then give integer numbers that we can work with in a range, where the lowest number is the order index set: 123456789 and the highest range (for N=9) is 987654321. Examining for N, you then get 12 - 21 123 - 321 1234 - 4321 and so on. Also, note that a valid permutation contains each index only once, and so you can disregard any number that does not contain one of the required indexes. Next, because of some interesting ways that number patterns happen, you can can observer that the difference between any adjacent unique index ordering must be a multiple of 9 (actually it is B-1, where B is the base of course, but here we are using base 10). Hence in our range, we can step every 9. There are actually much cooler patterns that you discover when you start to look at the interval between adjacent orderings: N=2: 9 N=3: 9, 81, 18, 81, 9 N=4: 9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9 N=5: 9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9, 5913, 9, 81, 18, 81, 9, 1602, 9, 261, 36, 63, 27, 594, 18, 162, 36, 162, 18, 603, 9, 171, 27, 72, 18, 5814, 9, 171, 27, 72, 18, 603, 9, 261, 36, 63, 27, 1584, 27, 63, 36, 261, 9, 603, 18, 72, 27, 171, 9, 5814, 18, 72, 27, 171, 9, 603, 18, 162, 36, 162, 18, 594, 27, 63, 36, 261, 9, 1602, 9, 81, 18, 81, 9, 5913, 9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9 (then the pattern gets too long for an email. You can see that there is a symmetry here. So, while I could take this further, it would probably bore the pants off everyone, so I won't. The upshot though is that if you are willing to waste some CPU cycles to get a really simple way of permuting, AND you don't need permutations for N>9, then you can use a really simple piece of code, that only takes any real time to run at N=9. Now, don't get me wrong, this is not the best algorithm by any means, just an interesting one, showing the side effects of being able to treat variables as integers and strings in jBC. In the code below there are also a few tricks used to allow the loop counter to remain an integer (internally), but otherwise it is simple enough to show without comments, so it can be practical in an email. I may write a C version callable from jBC for kicks :-) Jim --~--~---------~--~----~------------~-------~--~----~ Please read the posting guidelines at: http://groups.google.com/group/jBASE/web/Posting%20Guidelines IMPORTANT: Type T24: at the start of the subject line for questions specific to Globus/T24 To post, send email to [email protected] To unsubscribe, send email to [email protected] For more options, visit this group at http://groups.google.com/group/jBASE?hl=en -~----------~----~----~----~------~----~------~--~---
