Jim Idle wrote:
> 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
>
>
And this time with the jBC code ;-)
N = SENTENCE(1)
CRT "Permutations for N=":N
DIM List(10)
FOR I = 1 TO N
List(I) = "Element ":I
NEXT
IF N >9 THEN
CRT "Surely you're joking Mr. Idle?"
STOP
END
Start = "123456789"[1,N]
Limit = "987654321"[10-N,N]
Perms = 0
CRT "Loop from ":Start:" to ":Limit
FOR I = Start TO Limit STEP 9
J = I ;* Allow I to stay as an int
failed = 0
FOR K = 1 TO N
IF INDEX(J, K, 1) = 0 THEN
failed = 1
BREAK
END
NEXT
IF failed THEN CONTINUE
Perms++
CRT "Permutation ":J:" is ":
FOR E = 1 TO N
CRT List(J[E,1]):
IF E < N THEN CRT ", ":
NEXT
CRT
NEXT
CRT
CRT "There were ":Perms:" combinations."
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
