Re: all combinations from a set of numbers - Algorithms Discussion Boards

I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so...

Problem:
I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more)

the user will give in 3 number for example: 1 , 5 , 19

then the programme needs to give the following combinations:

1, 5, 19
1, 19, 5
5, 1, 19
5, 19, 1
19, 1, 5
19, 5, 1

I've been searching for some algoritme our other way to do this for several weeks now and just can't find it

any ideas on how I could achieve this??

If my help was helpfull let me know, if not let me know why.

The only way we learn is by making mistaks.

Hi,

if you want to list all combinations, recursion is what you need.
Build a method that takes a collection as an input, and let a for loop pick one element,
remove it, then call recursively with wath remains in the collection, until the collection
is empty; then return.

BTW: if your collection is ordered, and your method picks in that same order, the result will
be ordered too.

Warning: for n elements, the recursion depth will be n, the number of combinations n!

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google

Recursion is a bad thing. You can almost always remove recursion from an algorithm using a simple stack. Case in point, you can remove recursion from the suggested algorithm with a stack. Something like this:

1 on Stack
5 on Stack
19 on Stack
Start popping -> 1,5,19
19 on Stack
5 on Stack
Start popping -> 1,19,5

etc ...

HossFly

Hoss Fly wrote:
Recursion is a bad thing

Nonsense! Recursion is simply one tool that any professional should consider. There may be performance issues in some applications, but often you can't beat it for simplicity and elegance. Recursive descent parsing is an excellent example.

Hoss Fly wrote:
You can almost always remove recursion from an algorithm using a simple stack

So why not use the processor stack - i.e. recursion. If you use built-in support rather than roll your own stack the code may be cleaner and less error prone.

Unless the number of elements is large (in which case there is no point enumerating all n! permutations), recursion is a perfectly valid method of solution to consider.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...)

I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion.

It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.)

HossFly

I agree.

Steve

As Peter already told you, recursion has its merits; it is often abused, but in this case
it is the right approach. My last remark (the depth n and result count n!) was
intended to illustrate that: if you care to consume n! results, then a stack depth of n
would not be an obstacle.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google

<br />
char[] harfler = new char[7];<br />
                harfler[0] = tb1.Text.ToCharArray()[0];<br />
                harfler[1] = tb2.Text.ToCharArray()[0];<br />
                harfler[2] = tb3.Text.ToCharArray()[0];<br />
                harfler[3] = tb4.Text.ToCharArray()[0];<br />
                harfler[4] = tb5.Text.ToCharArray()[0];<br />
                harfler[5] = tb6.Text.ToCharArray()[0];<br />
                harfler[6] = tb7.Text.ToCharArray()[0];<br />
<br />
                List<string> liste = new List<string>();<br />
<br />
                for (int i = 0; i < harfler.Length; i++)<br />
                {<br />
                    for (int j = (i + 1) % 7, x = 0; x < harfler.Length; x++)<br />
                    {<br />
                        if (i != j)<br />
                        {<br />
                            for (int k = (j + 1) % 7, y = 0; y < harfler.Length; y++)<br />
                            {<br />
                                if (k != i && k != j)<br />
                                {<br />
                                    liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k]);<br />
                                    for (int l = (k + 1) % 7, z = 0; z < harfler.Length; z++)<br />
                                    {<br />
                                        if (l != i && l != j && l != k)<br />
                                        {<br />
                                            liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l]);<br />
                                            for (int m = (l + 1) % 7, t = 0; t < harfler.Length; t++)<br />
                                            {<br />
                                                if (m != i && m != j && m != k && m != l)<br />
                                                {<br />
                                                    liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m]);<br />
                                                    for (int n = (m + 1) % 7, v = 0; v < harfler.Length; v++)<br />
                                                    {<br />
                                                        if (n != i && n != j && n != k && n != l && n != m)<br />
                                                        {<br />
                                                            liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n]);<br />
                                                            for (int o = (n + 1) % 7, q = 0; q < harfler.Length; q++)<br />
                                                            {<br />
                                                                if (o != i && o != j && o != k && o != l && o != m && o != n)<br />
                                                                {<br />
                                                                    liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n] + "" + harfler[o]);<br />
<br />
                                                                }<br />
<br />
                                                                o = (++o) % 7;<br />
                                                            }<br />
                                                        }<br />
<br />
                                                        n = (++n) % 7;<br />
                                                    }<br />
                                                }<br />
<br />
                                                m = (++m) % 7;<br />
                                            }<br />
                                        }<br />
<br />
                                        l = (++l) % 7;<br />
                                    }<br />
                                }<br />
<br />
                                k = (++k) % 7;<br />
                            }<br />
                        }<br />
<br />
                        j = (++j) % 7;<br />
                    }<br />
                }<br />

Surely it is not an efficient way but in a specisific project this has worked well for me. It combinates 7 letters and produce words at least with length 3 and at most length 7.

.:: Something is Wrong ::.

Hmmm... that looks like permutations to me, not combinations. Smile | :)

In C++ something like this is the way to go:
--------------------------------------------

// Console.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <iterator>

void main()
{
using namespace std;

int Numbers[] = {1, 5, 19};
int *pOnePastEnd = Numbers + sizeof(Numbers)/sizeof(Numbers[0]);

sort(Numbers, pOnePastEnd);
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
while (next_permutation(Numbers, pOnePastEnd))
{
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
}
}

Steve

I see I got 2ed. Well it works perfectly and the OP didn't mention a language. If he's got a C++ compiler he can look in the source code and adapt the algorithm used to another language. Alternatively he could download STLport and do the same.

Steve

This is pseudocode for your solution:

ListCombinatoricalOrder(List L)
if (L is empty)
return

int n = L.Count
if (n == 1)
Write L[0]
return

Write(L)
ListCombinatoricalOrder(empty, L, n)
Done

ListCombinatoricalOrder(List Prefix, List comb, int count)
for (int i = 0; i < count; ++i)
List newPre = Prefix append comb[i]
List newComb = comb subtract comb[i]
if (i != 0)
Write(newPre, newComb)

ListCombinatoricalOrder(newPre, newComb, count - 1)
Done

WHERE:
Write(L) will write the entire list
Write(newPre, NewComb) will Write the list newPre then append the list NewComb to it

Notice the is an output generating algorithm not suited well for a library. But I left the details to you to make it more generic. This is just an idea of how to go about solving the combinatorical problem.

I hope this helps.
--Avi

-- modified at 4:42 Sunday 14th October, 2007

I have a set of machines, let's call them A,B,C,...etc and a bunch of tasks let's call them 1,2,3,...an so on. Now my machines aren't terribly reliable and often it may be the case that say A can do tasks 1 & 3, but can't do task 2, so obviously I shouldn't have it do task 2. Also each machine can only be assigned one task, so A can do 1 or 3, but not both. So let's say for example I have this:

A can do 1 & 3
B can do 1, 2 & 3
C can only do 3

The solution is obvious, A does 1, B does 2 and C does 3. This is fairly trivial for the case of only 3 machines and 3 tasks, but my real problem has 30 machines and potentially 30 tasks.
Is there an algorithm that handles these types of problems that somebody can point me in the direction of. It would need to suggest a solution (it's not necessary the case that any one solution would be better than another) or let me know that there is no solution and I need to fix my machines.
All I need is a nudge in the right direction.

Cheers!

Hungarian algorithm[^] maybe?

----

I don't care what you consider witty, but at least I do not blather on posting nonsense like Jim Crafton.
-- Stringcheese, humbled by Crafton's ability to string together multiple sentences

Thanks, I'll check it out.

Hello,

I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little...

First, let me define the terms I will use (a crash course in steel purchasing):
-Mill Order: simply an order of material placed to the steel mill
-Beams: should be self explanatory, but I want to cover their dimensioning:
-a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length.
Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number
of 1/16ths of an inch that make up the length. ->
For the sample, the length would be 1728 (1728/16)/12=9).)
-Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50
-Standard Size: any beam length 30ft-65ft in increments of 5ft.
-Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams.
-Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory
the extra.
a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you
4. But if you need 2, you must buy 3 and inventory the extra.
The bundle requirements change with each flange depth and weight.

Ok. Now to the logic bit...

I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle.

This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program.

I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or something of that nature. I DO NOT WANT SOURCE FROM ANY LANGUAGE.

Thank you in advance for your time and input,

-David

I think I might be able to help. Before we start, I have two observations:

[1] I take it that ordering the beams in a manner that is not suited to the design will result in someone at the site cutting / trimming / grinding each beam ordered to the beam design specs. If so, there are personnel charges, equipment usage, temporary storage locations, etc... that are costs to the company to make that happen. I do not see those costs in your description, and I wonder if sometimes the cost of buying a non-standard size/bundle is actually cheaper. I will ignore this complexity for now.

[2] Clearly, the problem is overwhelming you as it has too many parameters to jostle at once. A good problem solving strategy in such cases is to relax a few of the paramaters and get a solution for the relaxed problem. For example, I would start off assuming you are always ordering beams of the same nominal flange depth and the same pounds per foot. The examples discussed almost suggest you are indeed making this assumption, but I want to be clear. I would like to start here and steer you to a solution. Once we find a solution for this relaxed problem, we will add back one of the constraints and see what changes. We will then continue to iterativley add back in all the constraints until the original problem is solved. Is this approach ok?

HossFly

HossFly,

First of all, I cannot tell you how much I appreciate a timely and professional response. Such things are a rarity among most forums and message boards.

To address your first point raised; all cutting, grinding, welding, etc. is done by us in our shop. So the ammount of "shop hours" is billed seperately to the job. But that is a very good point I had not thought of.

As for your second point, yes, the problem is overwhelming me. I had thought of letting some of the parameters lie dormant for a short while, but it seems that every element of the problem is so closely related to the other - I am not quite sure of which parameters to drop. But I do like your recommendation of using the same beam size. I will try that and see if I can get a chunk of the problem diagrammed.

My biggest problem right now, is that I cannot seem to even write out on paper how this process works.

Thank you for your response,
-David

Alright, we can break the problem down even further. I do intend to honor your request and not provide source or solution, but rather help you attack the problem. Here is a suggested course.

Problem1:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there is only one standard size, and it is 30 ft.

Problem2:
[1] Assume Problem 1, but now allow for 30 ft or 35 ft standard sizes.

I think once you solve Problem1, and especially after you solve Problem2, you will understand how the 30-65 feet increments are impacting your solution. Let me know how that goes.

HossFly

I think you might be able to get a long way by using a multiple knapsack algorithm. The knapsack problem is to select a combination of N items with weights {Wi} to fill a knapsack with capacity K. The multiple knapsack problem tries to fill M knapsacks with capacities {Kj} from the N weights {Wi}. In your case the knapsacks are the available beamlengths. So if for one beam size the available beamlength is 20' and you need lengths {10', 6', 8', 12', 15', 2', 5', 7', 8'} then you need 73' of beam, so try to fill 4 knapsacks of 20'. If the algorithm fails, try to fill 5 etc...

One standard multiple knapsack code is http://www.netlib.org/toms/632[^].

Once you know how many beams you need you can then cope with bundling.

-- modified at 2:22 Saturday 22nd September, 2007

The multiple knapsack algorithm also allows you to include arbitrary beam lengths in your own inventory. So for the example given, if you had a 14' length of beam on hand, you could try to solve for 4 knapsacks {14, 20, 20, 20} and if this didn't work then add an additional 20' knapsack. This way you will continually use up your inventory

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

A request was made to give no source code, and it was requested in BOLD. Yet you gave a link to an algorithm and source. Incredible.

HossFly,

Thank you for helping me break down the problem like that. That was help much needed.

I think I have a good chunk figured out. I used one length and worked out how to nest the beams into that length with respect to bundling. It seems to be working very well, on paper. Right now, I input the beam(s) to be nested, and I nest them into lengths of 65', 60', 55', 50', 45', 40', 35', and 30' (all the standard lengths) one at a time. Each of the standard lengths is a function and returns two values; the total number of bundles (after making sure the beam meets the bundle requirements), and the amount of drop (unused portions of the beam(s) I am nesting into). Then I sort out which function returns the least amount of drop (as this will be the cheapest and most productive solution).

I think my next step is to do the same but for non-standard lengths (my only problem here is that I do not know how to round the lengths into even 6in. incriments). That way I can compare standard and non-standard prices. After that it's just a simple task of designing a report to output to the user.

But I still have questions about this method's efficency and/or actual optimization. Is there a test of some kind that you know of that can provide evidence for this? If not, don't worry about it.

Thank you again for breaking it down like that. I wish I had thought of that, but I guess that's why God didn't put me on the Earth by myself.

-David

Alright, we are getting closer. The next suggested steps would be:

Problem3:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there are only only non-standard sizes.

Problem4:
[1] Assume nominal flange depth and pounds per foot are fixed.
[2] Assume there is one standard size (e.g., 30') and non-standard sizes.

After you solve Problem4 you will then have unraveled another aspect of your algortihm (how the standard and non-standard sizes impact the logic.)

The big picture ...

I have often been in need of a niche-like algorithm similar in complexity to yours. I cannot count the times I have been frustratingly lost and on my own as well. My intent was not to give you fish, but rather share with you how I have caught several fish. You have used that now to (almost) catch your own fish, and that is very rewarding.

Sometimes you may not catch your fish, but by applying good problem solving skills (e.g., break down, relaxing conditions, combining sub-optimal sub-solutions, etc...), you gain the knowledge and understanding needed to realize what aspect of someone else's solution might work for you.

You will soon have your own algorithm. Not only that, you will have a deeper understanding of the mechanics of your problem. Having an algorithm is one thing - an optimal algorithm is another. Being able to analyze optimality requires intimacy with the problem. You are gaining this intimacy as well.

The standard means to measure optimality is to do a flop count (floating point operations). Some folk measure a "flop" as one addition and one multiplication. The idea is to then count the flops in your algorithm.

A good example is Matrix-Vector multiplication. To multiply an n-by-n matrix by a an n-vector would require roughly n^2 flops. Sometimes your matrix may have special properties (e.g., cyclic) and there are algorithms out there that can do the work in far less than n^2 flops.

I would suggest at least an attempt to count flops. This is a very difficult aspect of algorithm construction. Once you have completed your algorithm, and have been over the entire process with diligence, you will then be in a position to analyze the good/bad of a previous post about a possible alternative algorithm for you. I leave it to you to weigh the good and bad of that algorithm.

Best Regards,
HossFly

I suggested that a well-known algorithm may be applicable, and from the posting I guessed that the OP would not be aware that tried and tested source code was available - so I posted a link to one. It would be silly for a professional programmer to try to solve the multiple knapsack problem without at least considering the standard codes. Get offended if you like - it's your blood pressure.

From re-reading the original post, the fact that the standard lengths are not fixed but come in increments of 5' means that the multiple knapsack is not optimal. It would give you an efficient way of quickly testing different bundles - e.g. if you need 73' as in my example, you could try your inventory plus 3 lengths of 25', 3 of 30' and see if a solution existed.

If the number of lengths is small then the problem can be efficiently solved with an exhaustive search, but the complexity quickly escalates as the number of lengths increases.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Hey everyone,

I've been working on a bit of code that will calculate the time difference (hours/minutes) between two times, but only include business hours in that calculation. I have an iterative solution that works alright as long as "work hours" start and end on even hour boundaries. I could get the minute calculation to work by decreasing the size of my iterative step from hours to minutes, but it seems to me there must be a better way.

I've tried a couple of methods, and done some research on the problem, but haven't been able to come up with anything that really satisfies me. Any ideas?

Again, the problem in essence: calculate the amount of time (down to minutes) between two arbitrary date-times, counting only an arbitrary set of "working hours." All without simply looping over every minute in between start and end.

Don't sweat too much: at this point, it's more of an intellectual exercise than a practical necessity.

--
Chris Wilson