i am trying to predetermine all the possibilitees for this game i am trying to work on.. value is any number score must be any number <= value child has 1 score Group has any # of child(s) & all child(s) value in Group combined must equal value how do i find the number different possibilities?

You don't have many constraints :). The only thing that will limit you is the computer hardware.

All of your options are either infinity or negative infinity depending on the upper constraint (ie any number or <= value)

ok if there really is no way to figure out the number of possibilities that not too cool..
ill have to replan my whole life ;)

any ways..
if been trying to get Permutations to work..
but
n! / (n-k)!
does not work..
surely there is a way to figure it out

Lemme take a crack at it

The number of children in a group = n

for a childs score to find the possible outcome(?)

take the one extrem to the next so lets start with a basis

that no other people in the group so the score = group(1) = value

the other extreme would be score of group(n) = value - group(1 -> n-1) having each group member possibly having a score 0 -> value.

so if value = 1000, with 3 people

person 1 has score of 500
person 2 has score of 250
person 3 must have 250

So -----> group(n) = vale - (sum( i -> n - 1) { group(i) }) but each element has a possible combo(value, 1) then the next group would have combo(value - group(i-1),1)

try that

well.. im not sure exactly sure how to apply your equation

Quote:
so if value = 1000, with 3 people

person 1 has score of 500
person 2 has score of 250
person 3 must have 250

that above is correct



*There are "type" # of rows
*There are "unknown" # of columns (columns represent the possibilities)
*Sum of each Column must add up to "value"

here is a 2 small example of what i mean..
------------------------------------------------------
type = 2
value = 4

1| 4, 3, 2, 1, 0
2| 0, 1, 2, 3, 1

totalPossibilities = 5
-----------------------------------------------------
type = 4
value = 2

1| 2, 1, 1, 1, 0, 0, 0, 0, 0, 0
2| 0, 1, 0, 0, 2, 1, 1, 0, 0, 0
3| 0, 0, 1, 0, 0, 1, 0, 2, 1, 0
4| 0, 0, 0, 1, 0, 0, 1, 1, 1, 2

totalPossibilities = 10
--------------------------------------------------------

thanks for the help so far...

At first glance the equation: "(n-1+k)!/((n-1)!*k!)", where n is type and k is value, seems to do the trick.. Now just let me figure out why.. :)

EDIT: This has just occured to me, but do you actually need to calculate all the different combinations? If that's the case you can use a depth-first/backtracking recursive algorithm.

[Edited by - Devilogic on November 3, 2005 6:28:27 PM]

hehe nice..

"(n-1+k)!/((n-1)!*k!)" that works great.... as long as K is not that high of a number...if it is too high it flips out and returns 0

i may have done something wrong here
but this is what i got



i am pretty sure that the reason it flips out is because the value goes to high

well you can have higher k if you help computer a little bit like

ulong x = mulFromTo((coinTypes - 1) + coins,coins);
ulong y = factorial(coinTypes - 1);
ulong f = x / y;

ulong mulFromTo(long n,long m)
{
ulong k = (ulong)n - 1, total = (ulong)n;

while( k > m )
{
total *= k;
k--;
}
return total;
}

since n-1+k always higher than k ;)

Your implementation seems fine, but there are a few things that would make it safer..

1) Consider the equation "(5+2)!/5!". It is equivalent to "(1*2*3*3*4*5*6*7)/(1*2*3*4*5)", but which is also equivalent to simply "(6*7)".

Therefore it is prudent to break the equation "(n-1+k)!/((n-1)!*k!)" in two parts: "((n-1+k)!/(n-1)!) / k!". This is the equivalent of "((n-1+1)*(n-1+2)*...*(n-1+k-1)*(n-1+k)) / k!".

So your procedure would look something like this (sorry, but I'm not good at C):

var  X, Y, F: Integer;  I: Integer;begin  X := N;  for I:=N+1 to N+K-1 do    X := X*I;  Y := 1;  for Y:=2 to K do    Y := Y*I;  F := X div Y;end;

2) But notice that you now have two loops that iterate over the same number of elements (k-1 elements). Therefore you could write the procedure as:

var  F: Integer;  I: Integer;begin  F := N;  for I:=2 to K do    F := F*(I+N-1) div I;end;

This second way is safer than the first, because you divide as you go along.

Also notice that the above procedure uses an INTEGER divide (div), but that is justified, because "(a+1)*(a+2)*...*(b-1)*(b)" is always divisible by "(b-a)!", where "a" can be replaced by "(n-1)", and "b" by "i+n-1" (or "i+a").


EDIT: I've been writing this post for so long, that sakana321 beat me to the first half..

Now onto why the solution is in fact "(n-1+k)!/((n-1)!*k!)" (also written as a "C(n-1+k, k)", or the number of possible distributions without repetition of "n-1+k" elements into "k" groups).


1) Definitions:

In your case you say that the total value of all the children is "k" and that there are "n" children. Let's describe the value of the first child as "i(1)", the value of the second as "i(2)" and so on until "i(n)". Each child can only hold a nonnegative value ("i(j)>=0") and that value must be lower than, or equal to "k" ("i(j)<=k"); otherwise the total sum would be higher than "k".

The value of each child must also be a whole number (otherwise there would be an infinite number of possibilities).


2) Solution:

2.1) Suppose we write "k" as "k times 1" ("1+1+...+1+1" where "1" is repeated "k" times). Now, since each child can only hold a whole number the problem is reduced to distributing those "1"s among "k" children.

To illustrate: if the total value is "k=5=1+1+1 + 1 + 1+1" and we have "n=3" children, we can (for example) give the first child the value "i(1)=1+1+1", the second the value "i(2)=1", and the third the value "i(3)=1+1". The total number of 1s is preserved, and equals "k".


2.2) Now, let's lay out those 1s in a straight line, and place dividers ("|"s) between our "1"s to symbolize which child gets which 1s. We need to place "n-1" dividers between "k" 1s to completely describe the distribution of those 1s between "n" children. The final string is "n-1+k" long.

If we use the example above, we would describe that distribution as: "111|1|11".

(Note that the distribution "1111||11" is also valid and corresponds to "i(1)=4; i(2)=0; i(3)=2").


2.3) Now because "11|1" is not the same as "1|11" (in the first case the 1st child holds the value "i(1)=2", and in the second case the 1st child holds the value "i(1)=1"), the problem is reduced to picking places for "n-1" dividers among "n-1+k" possible places. We can do this in "C(n-1+k, n-1)" ways.


2.4) Because of the rule "C(n, r)=C(n, n-r)" we can write our equation "C(n-1+k, n-1)" also as "C(n-1+k, k)", which is the equation we postulated to be the correct one before we started.

This concludes our proof.


3) References:

"C(n+r-1, r)" is called a Combination with repetition.

- A good explanation of it, based on Euler's work, is given here (my proof was based mostly on this resource)
- As an alternate resource (but without explanation) look at Wikipedia's article Permuations and combinations

[Edited by - Devilogic on November 5, 2005 12:03:48 PM]