Math-sy question

Cheetah Designs said:
Im not bothered about running time, but I want it to be generic so that I can pass the algorithm four parameters.

- the minimum number
- the maximum number
- set min length
- set max length
Click to expand...

ok, its really not pretty, but heres a modification of my idea. i hope you're familiar with C because it was easier to write it in a style similar to C

Code: 
MinSetSize  //the smallenst number of numbers in your combinations, 5 in your example
MaxSetSize  //as above, but maximum, 10 in your example
CurrSetSize //the set size the program is looking for at the time

MinNumber   //the lowest number allowed in the set, 0 in your example
MaxNumber   //as above, but highest, 49 in your example



for(CurrSetSize = MinSetSize; CurrSetSize <=MaxSetSize; CurrSetSiz++)
{
	for(a = MinNumber; a <= MaxNumber; a++)
	{
		if(CurrSetSize = 1)
		{
			if(set is valid) //see earlier post
			{
				store set
			}
		}
		if(CurrSetSize > 1)
		{
			for(b = MinNumber; b <= MaxNumber; b++)
			{
				if(CurrSetSize = 2)
				{	
					if(set is valid) //see earlier post
					{
					store set
					}
				}
				if(CurrSetSize > 2)
				{
					etc, etc
				}
			}
		}
	}
}


the limit of the biggest set you can search for will be the number of 
nested for loops you've put in. because i havent copied and pasted 
much you;d only get sets of 1 or 2 from my program, but theoretically 
you could copy paste this as much as you like and get massive sets 9 
and kill your computer)

*edit*
what i've done is got the program to iterate through all the combinations for the minimum set size, then the minimum+1 set size, then minimum+2, all the way up to the maximum with the first for loop, and the if statements make sure it stops iterating through variables that arent in the set (eg, they stop the program for iterating through the 11th number combinations when you want to look through 10 number combinations). when it reaches the last number the if statements will store the combination if it is valid

there must be a way of doing this with recursive functions that wont involve 982736459623948562345 nested for loops, but i'm only a beginner at C/C++/C# so i wouldnt be sure of how to do it

i hope this helps though
 
Last edited:
Tbh you only need N nested loops, but you could use recursive functions if you keep a global array pointer going for your 'current' combination. That'll allow for any N as your number of elements. Then you just need to keep track of where you are in your combination with an integer as you go deeper into your recursion.

To be honest though in this instance i'd rather personally nest loops to avoid so many function calls.
 
Alex74 said:
Tbh you only need N nested loops, but you could use recursive functions if you keep a global array pointer going for your 'current' combination.
Click to expand...

If N can be any number, then the only way to do it is with a recursive function. (I think?)
 
if you're going to write it 'properly', then you abstract the steps.

You only need one loop and you apply some rules.
Code: 
void mainfunc()
{
  set currentSet = {0,1,2,3,4}

  while( notFinished(currentSet) )
  {
    set next = getNext(currentSet);
    print(next);
    currentSet = next;
  }

}

bool notFinished(set s)
{
  return s != {45,46,47,48,49};
}

set getNext(set s)
{
    // do the main logic here for adding to the last index and doing correct 'roll-over' etc etc
}


touch said:
If N can be any number, then the only way to do it is with a recursive function. (I think?)
Click to expand...
very wrong :p

You can calculate the end condition dynamically, given the min and max values of the main set, and the size of the required subset. Coding the 'logic' part I mention can be gone generally for any subset size.
 
Last edited:
Amleto said:
very wrong :p
You can calculate the end condition dynamically, given the min and max values of the main set, and the size of the required subset. Coding the 'logic' part I mention can be gone generally for any subset size.
Click to expand...

The size of the required subset is the 'N' i was referring to in my last post.
You need to calculate a different end condition for each possible size of the set.
So, if 'N' is an unlimited variable, you need to calculate any number of end conditions.


*Recursion might not be the only way to do it, i just meant that nested loops wont work.
 
Last edited:
Here's how I'd do it in Javascript (which i started learning about 2 weeks ago so might not follow standards!)

Code: 
//factorial function
function rFact(num)
{
    if (num === 0)
      { return 1; }
    else
      { return num * rFact( num - 1 ); }
}
// nCr function
function choose(n , r)
{
 return rFact(n)/( rFact(r)*rFact(n-r) );
}

//choose your variables
var totsize = 50;
var minsetlength = 5;
var maxsetlength = 10;
var totalcombos = 0;
var setcombo = 0;

//loop for sets between your limits
for (i=minsetlength;i<=maxsetlength;i++)
{
        var setcombo = choose(totsize,i);
        var totalcombos = totalcombos + setcombo;
}

console.log("For a set of " + totsize + " numbers, there are "+ totalcombos + " subsets between "+ minsetlength + " and "+maxsetlength);
 
touch said:
The size of the required subset is the 'N' i was referring to in my last post.
You need to calculate a different end condition for each possible size of the set.
So, if 'N' is an unlimited variable, you need to calculate any number of end conditions.


*Recursion might not be the only way to do it, i just meant that nested loops wont work.
Click to expand...

Not sure I understand you point in first para. For each N requested, there is exactly one end condition.

You don't need to pre-calculate *all possible* end conditions before the program starts for it to work in a general case.
 
Rollo said:
Here's how I'd do it in Javascript (which i started learning about 2 weeks ago so might not follow standards!)
Click to expand...

Thats good code considering you've only been at it for 2 weeks.

But the OP wants code that will generate each set, not just count the possibilities. (It was maybe my first post that put you wrong - i made the same mistake as well).
 
Last edited:
Amleto said:
Not sure I understand you point in first para. For each N requested, there is exactly one end condition.

You don't need to pre-calculate *all possible* end conditions before the program starts for it to work in a general case.
Click to expand...

In the example in the OP, he wants to find all sets between 5 and 10 numbers in length. You would need an end condition for each set length.

Or you could generate an end condition based on the current set length you are working on, but you'd need a lot more logic in your code to do that.
 
Last edited:
Ah well that's a bit harder! And for that reason, I'm out! :)

Out of interest what's significant about putting 20 into my rFact? Works fine.
 
Rollo said:
Out of interest what's significant about putting 20 into my rFact? Works fine.
Click to expand...

It looks fine to me. Very good considering you've only been at it a couple of weeks. I assume you have experience in other languages?

I'm not sure that you should have 'var' keywords inside the loop tho? I havnt really done much javascript so i could be wrong.
 
touch said:
haha :D this sounds like every programming project i get:

-Read the spec
"Yeah, that sounds easy...i'll get that done in a few days"
....a few days later
"hmmmm, there's more to this than i thought"
:p
Click to expand...

I didn't say it was complete. I said if N can be any number, you need one loop and some rules. That's still totally correct.

Saying I need more logic in my code that already says,
// do the main logic here ...

well, you don't get any marks for that :p
 
Amleto said:
I said if N can be any number, you need one loop and some rules. That's still totally correct.
Click to expand...


If N can be any single number, yes, you're right.
If N can be any range, like the example in the OP, you need more loopz :D

edit: actually, you'll probably still need another loop anyway if you want to dynamically create the end condition
 
touch said:
The size of the required subset is the 'N' i was referring to in my last post.
You need to calculate a different end condition for each possible size of the set.
So, if 'N' is an unlimited variable, you need to calculate any number of end conditions.
Click to expand...

You specified N is a number not a range. You cant change the definition of what N is and then argue a different point based on it :rolleyes::p
 
You must log in or register to reply here.
Back
Top Bottom