Help with an algorithm in C
Author 
Message 
Thorson MacAoid #1 / 61

Help with an algorithm in C
I am trying to write a program that takes a range of numbers and from that range finds all possible arrays of a defined size which contains all possible combinations of the numbers in that range where the following is true: 1. No number is repeated in any array. 2. The order of each number in the array is irrelavent. Example 1: given the number range of 1 through 4, and the defined array size is 4 places. The only possible combination is: 1 2 3 4 In this example the only possible array where all rules are satisfied is "1,2,3,4". Example 2: given the number range of 1 through 4, and the defined array size is 2 places. The possible combinations are: 1 2 1 3 1 4 2 3 2 4 3 4 any other combination would be a repeat of a previously stated combination, only in a different order. (e.g. 2 1 is simply the reverse of 1 2.) I am thinking that this may have to be written in several steps. One, to define all possible combination of the range of numbers. Two, to compare this list of arrays to find and remove all arrays where a number repeats within the array. Three, to compare the remainig arrays to find and remove all arrays where an array is simply a repeat of another array in a different order. I am looking for suggestions and or a voice of experience in processing numbers in this fashion. Thanks Thorson MacAoidh 

Wed, 26 Feb 2003 13:07:52 GMT 


Francis Glassboro #2 / 61

Help with an algorithm in C
Quote: >I am looking for suggestions and or a voice of experience in processing >numbers in this fashion.
This seems awfully like homework to me. Try thinking about recursion. Francis Glassborow Association of C & C++ Users 64 Southfield Rd Oxford OX4 1PA +44(0)1865 246490 All opinions are mine and do not represent those of any organisation 

Thu, 27 Feb 2003 00:51:29 GMT 


Peter Burk #3 / 61

Help with an algorithm in C
Quote:
> I am trying to write a program that takes a range of numbers and from that > range finds all possible arrays of a defined size which contains all > possible combinations of the numbers in that range where the following is > true: > 1. No number is repeated in any array. > 2. The order of each number in the array is irrelavent. > Example 1: > given the number range of 1 through 4, and the defined array size is 4 > places. The only possible combination is: > 1 2 3 4 > In this example the only possible array where all rules are satisfied is > "1,2,3,4". > Example 2: > given the number range of 1 through 4, and the defined array size is 2 > places. The possible combinations are: > 1 2 > 1 3 > 1 4 > 2 3 > 2 4 > 3 4 > any other combination would be a repeat of a previously stated combination, > only in a different order. > (e.g. 2 1 is simply the reverse of 1 2.) > I am thinking that this may have to be written in several steps. > One, to define all possible combination of the range of numbers. > Two, to compare this list of arrays to find and remove all arrays where a > number repeats within the array. > Three, to compare the remainig arrays to find and remove all arrays where an > array is simply a repeat of another array in a different order. > I am looking for suggestions and or a voice of experience in processing > numbers in this fashion.
This isn't a C question at all, but here are some hints. #1  you said that order doesn't matter. Is there a particular order that you could use that would make the job easier? #2  from example 2, once you've figured out (1 2) (1 3) (1 4), are there any other arrays of size 2 which contain a '1'? Can you use this to your advantage? #3  think about using recursion to solve this. What happens if you tack 1 onto the beginning of each array of size 1 from the range 24? How about putting 2 onto the beginning of each array of size 1 from the range 34? #4  you don't need any auxillary storage, other than the machine stack, to solve this problem. /peter 

Thu, 27 Feb 2003 00:52:06 GMT 


Tristan Wibberle #4 / 61

Help with an algorithm in C
Quote:
>I am trying to write a program that takes a range of numbers and from that >range finds all possible arrays of a defined size which contains all >possible combinations of the numbers in that range where the following is >true:
This isn't really a C question, it's maths. Look up "nCr" (n is superscript, r is subscript). It uses factorials and the C implementation is too simple to be anything but homework.  Tristan Wibberley 

Fri, 28 Feb 2003 22:07:56 GMT 


Brian Ingli #5 / 61

Help with an algorithm in C
On 09 Sep 2000 05:07:52 GMT, "Thorson MacAoidh" Quote:
>I am trying to write a program that takes a range of numbers and from that >range finds all possible arrays of a defined size which contains all >possible combinations of the numbers in that range where the following is >true: >1. No number is repeated in any array. >2. The order of each number in the array is irrelavent. >Example 1: >given the number range of 1 through 4, and the defined array size is 4 >places. The only possible combination is: >1 2 3 4 >In this example the only possible array where all rules are satisfied is >"1,2,3,4". >Example 2: >given the number range of 1 through 4, and the defined array size is 2 >places. The possible combinations are: >1 2 >1 3 >1 4 >2 3 >2 4 >3 4 >any other combination would be a repeat of a previously stated combination, >only in a different order. >(e.g. 2 1 is simply the reverse of 1 2.) >I am thinking that this may have to be written in several steps. >One, to define all possible combination of the range of numbers. >Two, to compare this list of arrays to find and remove all arrays where a >number repeats within the array. >Three, to compare the remainig arrays to find and remove all arrays where an >array is simply a repeat of another array in a different order. >I am looking for suggestions and or a voice of experience in processing >numbers in this fashion. >Thanks >Thorson MacAoidh
For the number of combinations of k objects picked from a set of n objects, calculate the binomial coefficient: ( n ) n! ( ) =  ( k ) k!(nk)! where ! is the factorial operator: __ m! = II m = m x (m1) x ... x 2 x 1 e.g. 4!/2!(42)! = 4!/2!2! = 24/2.2 = 24/4 = 6 the same answer you got by enumeration. See any stats text or Knuth TAoCP vol.1 (3rd ed.) 1.2.6 p.55. Thanks. Take care, Brian Inglis Calgary, Alberta, Canada 
use address above to reply 

Fri, 28 Feb 2003 22:09:57 GMT 


Tristan Wibberle #6 / 61

Help with an algorithm in C
Quote:
>>I am trying to write a program that takes a range of numbers and from that >>range finds all possible arrays of a defined size which contains all >>possible combinations of the numbers in that range where the following is >>true: >This isn't really a C question, it's maths. Look up "nCr" (n is superscript, >r is subscript).
Oops, you wanted to enumerate the combinations didn't you, not find how many there are. Sorry everyone. Still, you can use this to great advantage in the algorithm you create to avoid having n iterators.  Tristan Wibberley 

Sun, 02 Mar 2003 03:39:24 GMT 


Thorson MacAoid #7 / 61

Help with an algorithm in C
Thanks for the math lesson, and the direction to TAoCP. I will take a look at this page in Knuth's book. Thanks Thorson MacAoidh Quote:
>For the number of combinations of k objects picked from a set of >n objects, calculate the binomial coefficient: >( n ) n! >( ) =  >( k ) k!(nk)! >where ! is the factorial operator: > __ >m! = II m = m x (m1) x ... x 2 x 1 >e.g. 4!/2!(42)! = 4!/2!2! = 24/2.2 = 24/4 = 6 >the same answer you got by enumeration. >See any stats text or Knuth TAoCP vol.1 (3rd ed.) 1.2.6 p.55. >Thanks. Take care, Brian Inglis Calgary, Alberta, Canada >
> use address above to reply >


Sun, 02 Mar 2003 03:39:31 GMT 


Thorson MacAoid #8 / 61

Help with an algorithm in C
Quote: >This seems awfully like homework to me. Try thinking about recursion.
What are you meaning by the term recursion? Unfortunately I do not have the benefit of a classroom as a forum for my questions. Nor do I have the benefit of instruction in the arts of computer programming. I appologize to all who feel that my question is not derserving of help due to the seemingly "simple" nature of the C implementation for my algorithm. In any case, I appreciate fully all information that has been afforded me here in this forum. Thanks Thorson MacAoidh 

Sun, 02 Mar 2003 03:39:37 GMT 


Thorson MacAoid #9 / 61

Help with an algorithm in C
See Below. Quote: >This isn't really a C question, it's maths. Look up "nCr" (n is superscript, >r is subscript).
I appreciate this tidbit of information. Are you referring to a particular library, when you make reference to "maths?" Quote: >It uses factorials and the C implementation is too simple to be anything but >homework.
Unfortunately I do not have the benefit of a classroom as a forum for my questions. Nor do I have the benefit of instruction in the arts of computer programming. I appologize to all who feel that my question is not derserving of help due to the seemingly "simple" nature of the C implementation for my algorithm. In any case, I appreciate fully all information that has been afforded me here in this forum. Thanks Thorson MacAoidh 

Sun, 02 Mar 2003 03:39:49 GMT 


Thorson MacAoid #10 / 61

Help with an algorithm in C
See Below. Quote:
>This isn't a C question at all, but here are some hints. >#1  you said that order doesn't matter. Is there a particular >order that you could use that would make the job easier?
Yes, I think that I understand this. Quote: >#2  from example 2, once you've figured out (1 2) (1 3) (1 4), >are there any other arrays of size 2 which contain a '1'? Can >you use this to your advantage?
Yes, and I believe that I understand this as well. Quote: >#3  think about using recursion to solve this. What happens if >you tack 1 onto the beginning of each array of size 1 from the >range 24? How about putting 2 onto the beginning of each array >of size 1 from the range 34?
This is where I get confused. First, what is meant by the term "recursion?" Are you referring to a specific methodology defined by imbedded conditional statements? e.g. for(conditions){ for(more conditions){ do this; } } Or am I missing this altogether? Second, I do not quite get what you are saying about tacking number to the beginning of an array. I am seeing this as something like the following: 1. Change of rules: array is size 3 number range is 59. this would give me, if I started with a size 1 array of numbers 69 and "tack" 5 onto the beginning, the following: 56 57 58 59 Now with 79 tacking 6: 67 68 69 etc.... 2. Now with all of the possible size 2 arrays known, I could begin again by starting to tack all the individual digits to the beginning of all of the know size 2 arrany combinations. Or, I could start by tacking the number to the end, eg: 567 568 569 577 578 579 587 588 589 597 598 599 etc..... (Of course many of these would fail a duplicity test, and would therefore be invalid arrays.) This sould also keep some order to database of arrays. If I created the db with this method no number in a particular space in an array would be smaller than the number than of space1. Oops. Let me rephrase, the value of array[2] would have to be larger than values of array[0] or array[1]. Thorson MacAoidh PS. Unfortunately I do not have the benefit of a classroom as a forum for my questions. Nor do I have the benefit of instruction in the arts of computer programming. I appologize to all who feel that my question is not derserving of help due to the seemingly 

Sun, 02 Mar 2003 03:39:55 GMT 


Michael Tiomki #11 / 61

Help with an algorithm in C
Quote: > On 09 Sep 2000 05:07:52 GMT, "Thorson MacAoidh"
> >I am trying to write a program that takes a range of numbers and from that > >range finds all possible arrays of a defined size which contains all > >possible combinations of the numbers in that range where the following is > >true: > >1. No number is repeated in any array. > >2. The order of each number in the array is irrelavent. > > ...... > >I am looking for suggestions and or a voice of experience in processing > >numbers in this fashion. > >Thanks > >Thorson MacAoidh > For the number of combinations of k objects picked from a set of > n objects, calculate the binomial coefficient: > ( n ) n! > ( ) =  > ( k ) k!(nk)! > where ! is the factorial operator: > __ > m! = II m = m x (m1) x ... x 2 x 1 > e.g. 4!/2!(42)! = 4!/2!2! = 24/2.2 = 24/4 = 6 > the same answer you got by enumeration. > See any stats text or Knuth TAoCP vol.1 (3rd ed.) 1.2.6 p.55. > Thanks. Take care, Brian Inglis Calgary, Alberta, Canada > 
> use address above to reply
Well, he wanted to find the sequence of all these sets, and not the size of this sequence. To do this, you can use a simple recursive algorithm. Below I'll use notation that is not strictly C!) Sequence<Set<El>> subsets_of_size( Set<El> src, int sz) { if (sz < size(src)) return []; // empty sequence if (sz == size(src)) return [src]; // single element sequence El first_elem = src[0]; Set<El> src2 = src \ {first_elem}; // copy src and delete its first element // the case that first_elem belongs to the result set Sequence<Set<El>> reslt = subsets_of_size(src_2, k1); for (int i=0; i < size(reslt); ++i) reslt[i].append(first_elem); // the case that first_elem doesn't belong to the result set reslt += subsets_of_size(src_2, k); // + is the union of two sequences return reslt; Quote: }
Notice also that this algorithm only uses suffixes of the initial set, and you can use indices/iterators to represent the suffixes, avoiding copying sets. BTW, I don't want to start language war here, but this algorithm will look much simpler in C++ (using standard library), and not C. MIchael 

Sun, 02 Mar 2003 03:41:13 GMT 


Bruce G. Stewar #12 / 61

Help with an algorithm in C
Quote:
> >This seems awfully like homework to me. Try thinking about recursion. > What are you meaning by the term recursion? > Unfortunately I do not have the benefit of a classroom as a forum for my > questions. Nor do I have the benefit of instruction in the arts of computer > programming. I appologize to all who feel that my question is not derserving > of help due to the seemingly "simple" nature of the C implementation for my > algorithm. In any case, I appreciate fully all information that has been > afforded me here in this forum.
Recursion, in programming, generally refers to a function which is implemented in part by calling itself with different arguments. The classic example is the function factorial, which is mathematically defined as: 1 factorial, written 1!, is 1 n!, where n>1, is n * (n1)! An implementation based directly on this definition is int factorial(int n) { if (n == 1) return 1; else if (n > 1) return n * factorial(n1); else exit(EXIT_FAILURE); /* fail  undefined */ Quote: }


Sun, 02 Mar 2003 22:13:52 GMT 


Michiel Salter #13 / 61

Help with an algorithm in C
Quote:
> >This seems awfully like homework to me. Try thinking about recursion. > What are you meaning by the term recursion? > Unfortunately I do not have the benefit of a classroom as a forum for my > questions. Nor do I have the benefit of instruction in the arts of computer > programming. I appologize to all who feel that my question is not derserving > of help due to the seemingly "simple" nature of the C implementation for my > algorithm. In any case, I appreciate fully all information that has been > afforded me here in this forum. > Thanks > Thorson MacAoidh
Recursion is the process of solving a problem by repeatedly reducing it to a smaller problem until you got a problem you know the solution of. A simple example is the factorial function: 1! = 1, 2! = 1*2, 3!=1*2*3, 4!=1*2*3*4. Now how can we calculate n! ? In C, we could write this using a loop (iterative , not recursive) int factorial(int n) { int result =1; while (n) result = result * n; return result; Quote: }
We can also use the fact that n! = n* (n1)! int factorial (int n) { if n=1 return 1; else return n*factorial(n1); Quote: }
The latest form is recursion: We know the solution for n=1, and we can express the solution for n>1 in terms of the solution for n1. Back to your problem, in your case you "recurse" on the number of elements. Picking one element is simple. Now, how do you get from a selection of N1 elements to a selection of N elements? Quote: >From there, you should be able to create a design yourself.
HTH, Michiel Salters 

Mon, 03 Mar 2003 03:00:00 GMT 


Michiel Salter #14 / 61

Help with an algorithm in C
[ in too big a hurry ] Quote: > We can also use the fact that n! = n* (n1)! > int factorial (int n) > { > if n=1 return 1; > else return n*factorial(n1); > } > The latest form is recursion: We know the solution for n=1, > and we can express the solution for n>1 in terms of the solution > for n1.
Since 0! = 1, and n=1 is always true :( ,and 1 is undefined, the functions should have been: unsigned long factorial (unsigned int n) { if n<=1 return 1; else return factorial(n1)*n; Quote: }
Spotting the missing '<' is probably a bit hard for people who're learning recursion. Michiel Salters 

Tue, 04 Mar 2003 03:00:00 GMT 


