All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info
Discussion Forums
Login: Password:Remember me: Sign up! | Forgot password

Forums > Reference
This is a place to ask questions about math terminology, and to post links to other resources out on the web.
Axorion
2007-11-19 11:48:30
Coding factorials

I've been looking around the site at some of the coded solutions. I've noticed a lot of "brute force" programming using heavily nested loops and contingent then if statements. I've always liked a more elegant approach. In that light here's some functions I've coded in visual basic that might make your code more readable by the other members. If someone wants to post similar function in C++ or using arrays instead of strings, I'm sure they will be appreciated.

The following code takes a seed string and an index. It will return the string with the characters reordered based on the index. If the length of the seed is n then valid values for the index are 0 to n!-1.

Function factorrange(ByVal seed As String, ByVal index As Integer) As String

Dim buffer As String
Dim pointer As Integer
Dim counter As Integer
Dim place As Long
Do While index < 0
index = index + factorial(Len(seed))
Loop
index = index Mod factorial(Len(seed))
For counter = 1 To Len(seed) - 1
place = factorial(Len(seed) - 1)
pointer = index \ place + 1
buffer = buffer + Mid(seed, pointer, 1)
seed = Left(seed, pointer - 1) + Mid(seed, pointer + 1)
index = index Mod place
Next counter
factorrange = buffer + seed

End Function

Function factorial(ByVal n As Integer) As Long

Dim product As Long
product = 1
For n = 1 To n
product = product * n
Next n

End Function

Now every possible ordering of "123456789" or "ABCD" can be coded as follows.

Const data = "123456789"
Rem Const data = "ABCD"
For n = 0 To factorial(Len(data)) - 1
test_something (factorrange(data, n))
Next n

This is much easier to read and understand.

brianjn
2007-11-19 18:34:46
Re: Coding factorials

There are some programs on site which have used Visual Basic. Most of those to which you refer are written in QBasic. Yes, it may not have the elegance one would expect from the point of view of an accomplished, more sophisticated programmer. I am not suggesting that author is not of that calibre; depending upon his purpose he selects a vehicle which is adequate for his purpose at the time.


There also seem to few here with much depth in programming skill anyway so I appreciate being able to read the usually self-explicit variables and see the structural flow.


I'll leave further comment to others more qualified to address this.

Brian Smith
2007-11-20 01:57:03
Re: Coding factorials

I use the code structure below when I need to create all permutations of 1 to N. One thing to note, the permutations are not in ascending or descending order. Instead, each entry differs from the previous by a single interchanged pair.

10 N = 10: REM permutation program: permutes N objects (0 to N-1)
20 DIM P(N): DIM A(N)
30 FOR I = 0 TO (N - 1)
40 P(I) = I: A(I) = I
50 NEXT I
60 I = 1: GOSUB 200
70 IF (P(I) = 0) THEN 140
80 P(I) = P(I) - 1
90 J = (I MOD 2) * P(I)
100 T = A(I): A(I) = A(J): A(J) = T
110 GOSUB 200
120 I = 1
130 GOTO 160
140 P(I) = I
150 I = I + 1
160 IF (I < N) THEN 70
170 PRINT : PRINT "Done": END
200 REM Do something with array A()
299 RETURN

I also have a version in C for when I need more speed than what interpreted BASIC can yield.

brianjn
2007-11-20 02:34:17
Re: Coding factorials

GWBasic?

brianjn
2007-11-20 02:57:51
Re: Coding factorials

There is another consideration [re my earlier dialogue] to which I hadn't given a great deal of thought. The program listings offer proof that presented data was not 'contrived', and since the goal was to get a result, then the simplest available method has to suffice.


Additionally, QBasic came as part of the MSDOS 5 and 6 OS's (Yes, I'm talking pre-Windows) so it was widely distributed though probably seldom used to its potential.


That some of us may have the software laying around means that in many cases we can copy and paste these listings and run them for our own verification. As some are written to access specific data files they of course are useless to us, but we usually accept that the listing is sufficient justification.


If you care to browse the Forums, and I'm not sure where you'll find it, but the director once offered a section on programming problems (it may be in the only 'protected' forum on Perplexus accessible once you get to Apprentice, unsure).

The floated idea, as I recall, was not to specifically write a program for an 'event' but rather to propose strategies. The category "Algorithms" seemed to best fit the dialogue of the time; there was also mention of the different "flavours" of programming which seemed to influence this idea not being followed.


I'd like to make just one more point. While the listings here are generally not those demanded by programmers of the highly structured languages, they have value in demonstrating to a beginner programmer elements and blocks within the task, the implementation of logical operators, and yes, subroutines/functions [can't specifically recall a SUB......END SUB].

Brian Smith
2007-11-20 11:53:11
Re: Coding factorials

The code segment I posted above was used in QBasic, but I think it would run in UBasic that Charlie uses quite often.

I managed to find QBasic buried in Windows 95.

Axorion
2007-11-20 16:15:29
Who can run16 bit

I wrote my share of QBASIC code. QBASIC runs on a 16 bit OS. I haven't had a 16 bit OS for 7 years. My current setup is 64 bit. It's good that this site is accessible to everyone. Learning is to often held back due to lack of money. Having said that, I would hate to have to go back to line numbers and gosub statements.

If you have a 32 bit OS and broadband you can get VB5 CCE free and legal here.
http://www.thevbzone.com/vbcce.htm

If you like the C syntax better try Borland JBuilder Personal.
http://info.borland.com/new/jdj_personal.html

Python is free and legal.
http://www.python.org/download/

There are others. If you don't have broadband but do have a credit card, I think anyone of these cost around $15 on CD.

Finally, If you have a browser that runs scripts and a text editor you have a better version of basic than QBASIC. Although, if you want to use GUI objects you might want to brush up on your HTML.

Axorion
2007-11-20 16:49:19
Re: Coding factorials (FIX)

Just banged this code out yesterday. It needs a few updates.

Critical: index as long (not integer)
Function factorrange(ByVal seed As String, ByVal index As Long) As String

Optimization: Limit Checking
Change...
Do While index < 0
index = index + factorial(Len(seed))
Loop
index = index Mod factorial(Len(seed))
To...
index = index Mod factorial(Len(seed))
If index < 0 Then index = index + factorial(Len(seed))

Charlie
2007-11-21 09:20:18
Re: Coding factorials

You might want to post your algorithm as a solution to Permutations, http://perplexus.info/show.php?pid=986, as, I take it it's a solution to the permutation problem rather than a factorial problem.

Charlie
2007-11-21 09:28:03
Re: Coding factorials

16-bit Qbasic runs in a Command prompt within any version of Windows. Same for UBASIC and GWBasic, though I don't know why you'd want to use that last one.

Charlie
2007-11-21 09:47:51
Re: Coding factorials

Don't you also need a "Factorial = product" just before the "end function" in the factorial function?

Charlie
2007-11-21 09:59:13
Re: Coding factorials

Here's the QBasic version, or more specifically, the Quick Basic version. QBasic was a slowed down version that came with some versions of DOS. Quick Basic was a commercial product that sold for 70 or 80 dollars and was about 5 times as fast as the QBasic packaged with DOS.

DECLARE FUNCTION perm$ (seed AS STRING, index AS LONG)
DECLARE FUNCTION factorial& (N&)
CLS
a$ = "abcde"
FOR i = 1 TO factorial(5)
PRINT perm$((a$), (i)); " ";
NEXT

DEFLNG A-Z
FUNCTION factorial (N)
DIM product AS LONG

product = 1
FOR N = 1 TO N
product = product * N
NEXT N

factorial = product
END FUNCTION

FUNCTION perm$ (seed AS STRING, index AS LONG)
DIM buffer AS STRING
DIM pointer AS INTEGER
DIM counter AS INTEGER
DIM place AS LONG



index = index MOD factorial(LEN(seed))

IF index < 0 THEN index = index + factorial(LEN(seed))
FOR counter = 1 TO LEN(seed) - 1
place = factorial(LEN(seed) - 1)
pointer = index \ place + 1
buffer = buffer + MID$(seed, pointer, 1)
seed = LEFT$(seed, pointer - 1) + MID$(seed, pointer + 1)
index = index MOD place
NEXT counter
perm$ = buffer + seed


END FUNCTION

Charlie
2007-11-21 10:02:19
Re: Coding factorials

The parentheses around the arguments in the call to perm$ take the place of the BYVAL in the argument list within the function. Usually I get around the necessity for that by transferring parameter values to local variables within the function. In QB, mid and left need their $ string signifiers.

Charlie
2007-11-21 10:05:46
Re: Coding factorials

Advantage of Axorion's method: can get at nth permutation without going through the first n-1).

Disadvantage: When permuting a string with duplicates, it doesn't skip over duplicated permutations, and all n$ have to be gone through to get all the permutations.

Axorion
2007-11-21 20:58:49
Yes Charlie

Yes Charlie the "Factorial = product" is missing. I don't know how that happened. I copied and pasted it right out of Visual Basic. I wish the forums had the same capability to edit posts as the puzzles.

You are right about duplicates, however, the max string length of 12 caused by the long type used for indexing seems to be to be a bigger draw back to me.

I'm going to check out pid=986 now. If I post it there I'll be sure to get it right.

Axorion
2007-11-22 17:18:53
Re: Coding factorials

Sorry, I forgot that QBASIC was a structured language. I must have been thinking of GWBASIC. Anyway, I still can't run QBASIC on my XP64. I get the following error message.

The image file QBASIC.EXE is valid, but is for a machine type other than the current model.

I get a similar message when attempting to run any DOS program. I'm sure it would run if I downloaded a free DOS emulator. Then again, if I need to download something why not just download a free copy of visual basic.

Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information