forums.silverfrost.com Forum Index forums.silverfrost.com
Welcome to the Silverfrost forums
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Permutations and combinations with a trolley!

 
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General
View previous topic :: View next topic  
Author Message
Notquitenewton



Joined: 25 May 2021
Posts: 20
Location: England, UK

PostPosted: Sun Jan 02, 2022 4:14 pm    Post subject: Permutations and combinations with a trolley! Reply with quote

A bit late but seasons greetings...the blurb under the line Selection.for hopefully explains what I've been trying to do! This problem has no doubt been looked at by better folk than I and with much faster code!
The code seems to run ok and gives the right answers but as the the no. of objects increases the time taken becomes crazy, mainly due to the numbers involved. If anyone has the time or inclination, could you make some suggestions how to speed this up please? The objects placed on a trolley are 1-D (length) at present, so my next escapade will be to do this in 2-D (length and width).
I thought this might be tricky but it is turning out to be very tricky indeed!!

I'm using FTN95 (64-bit option) Vers. 8.8
Many thanks
Notquitenewton

C
C Program: Selection.FOR
C
C Program to make selection of a number of objects from a total
C pile of objects and see if they will fit on a trolley!
C To avoid taking too long, restrict the total number (n) to
C <= 30. At a first attempt try n = 10 to check it's ok. As n
C increases, the number of calculations begins to escalate
C rapidly. The idea is to generate objects of different lengths and
C see which combinations will fit on a trolley of known length.
C Not quite as simple as it first appeared!
C The length of each object is stored in array length() and it's
C reference is used as a pointer in array itempointer().
C The lengths of the items are generated randomly (or the same)
C and will be between ilow and ihigh. The min. amount of trolley
C is stored in imin.
C The other two routines calculate the no. of permutations and
C the combinations using factorials.
C The routines are compiled using FTN95 with /WIN/64 and linked
C using SLINK64 to make the 'selection.exe' file.
C After a run, the results are stored in file Results001.txt which
C should be in the same directory as the program.
C

Link for full code is

https://www.pcmodfit.co.uk/Selection.for

Notquitenewton


Last edited by Notquitenewton on Sun Jan 02, 2022 5:28 pm; edited 1 time in total
Back to top
View user's profile Send private message
wahorger



Joined: 13 Oct 2014
Posts: 1214
Location: Morrison, CO, USA

PostPosted: Sun Jan 02, 2022 4:49 pm    Post subject: Reply with quote

Packing algorithm challenge to start 2022!

I have a similar need, but in 2-D. There are numerous packing algorithms that one can find on-line. Most that I have found require that the algorithm run as a recursive algorithm. FTN95 can certainly do that part.

One thing FORTRAN is not designed to do is to define a "class" for the data and attach operations to accomplish the packing. The "trick" would be to define the "C++" class as a Fortran construct. There just isn't any reasonable to do that for the algorithms I have found.

Some of the 2-D algorithms target packing the objects in order to minimize the resulting area. One I ran across: https://flipcode.com/archives/Rectangle_Placement.shtml

My specific problem is more like packing the bottom of a utility trailer, where the size (length and width) of the trailer is fixed, the width of each object is fixed, and the length of each object is variable. You're looking to maximize the number of objects that can be packed onto the trailer, minimizing the uncovered "floor".

I look forward to your solution!
Back to top
View user's profile Send private message Visit poster's website
mecej4



Joined: 31 Oct 2006
Posts: 1884

PostPosted: Sun Jan 02, 2022 6:22 pm    Post subject: Reply with quote

Two suggestions.

A. Do not perform a lot of screen output, especially when you are already doing the same output to a file. Such output is only useful when debugging with small data sets.

B. Instead of calculating nCr by calling the factorial function three times, try the following:
Code:
real function nCr(n,r)
implicit none
integer n,r,i
!
ncr=n
do i=2,min(r,n-r)
   ncr=ncr*(n+1-i)/i
end do
end function nCr


Note: You called the nCr function "permutate", but the formula is for combinations.
Back to top
View user's profile Send private message
Notquitenewton



Joined: 25 May 2021
Posts: 20
Location: England, UK

PostPosted: Mon Jan 03, 2022 4:49 pm    Post subject: Reply with quote

Hi mecej4,
Thanks for the comments...
I only use screen output for debugging (forgot to comment out).
Tried your suggested little bit of code and bingo...goes much more like a rocket. With small numbers of n there isn't much difference as one would expect but as n increases the time difference is excellent indeed, At n >50 I note a speeding up over 1000x and even more so as n approaches 100.
Really chuffed with your help, so thanks very much indeed!
There is just one routine now instead of the previous three.
Regards
Notquitenewton

The single file is linked to...

https://www.pcmodfit.co.uk/Selection.for

for download if you'd like a copy (or anyone else)
Back to top
View user's profile Send private message
Robert



Joined: 29 Nov 2006
Posts: 444
Location: Manchester

PostPosted: Tue Jan 04, 2022 7:03 pm    Post subject: Reply with quote

Can't you simulate what a C++ class does with a TYPE and a module? The TYPE contains the data and the module contains the methods that operate on the type? I am assuming here there is no inheritance in the classes...
Back to top
View user's profile Send private message Visit poster's website
wahorger



Joined: 13 Oct 2014
Posts: 1214
Location: Morrison, CO, USA

PostPosted: Sat Jan 08, 2022 8:49 pm    Post subject: Reply with quote

Robert, you may be able to do this; I don't see why it cannot be done. I will not claim to be familiar with the use of MODULE's and what limitations there might be.

I have created several DLL's using MINGW and CodeLite to compile and link to FTN95 many public domain and Open Source "C" and C++. I would be likely to do that again rather than try to recode/port a large amount of C++ code to FTN.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    forums.silverfrost.com Forum Index -> General All times are GMT + 1 Hour
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group