Permutations and combinations with a trolley!

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

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!

Two suggestions.

1. 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.

2. Instead of calculating nCr by calling the factorial function three times, try the following:

   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.

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)

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...

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.