Help with an algorithm in C
Author Message 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  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  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 2-4?  How about putting 2 onto the beginning of each array
of size 1 from the range 3-4?

#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  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  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!(n-k)!

where ! is the factorial operator:
__
m! = II m = m x (m-1) x ... x 2 x 1

e.g. 4!/2!(4-2)! = 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  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  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!(n-k)!

>where ! is the factorial operator:
>     __
>m! = II m = m x (m-1) x ... x 2 x 1

>e.g. 4!/2!(4-2)! = 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  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  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  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 2-4?  How about putting 2 onto the beginning of each array
>of size 1 from the range 3-4?

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 5-9.
this would give me, if I started with a size 1 array of numbers 6-9
and "tack" 5 onto the beginning, the following:
56    57    58    59
Now with 7-9 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:
56-7    56-8    56-9
57-7    57-8    57-9
58-7    58-8    58-9
59-7    59-8    59-9
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 space-1. Oops. Let me rephrase, the value of
array would have to be larger than values of array or array.

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  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!(n-k)!

> where ! is the factorial operator:
>      __
> m! = II m = m x (m-1) x ... x 2 x 1

> e.g. 4!/2!(4-2)! = 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;
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, k-1);
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  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 * (n-1)!

An implementation based directly on this definition is

int factorial(int n)
{
if (n == 1)
return 1;
else if (n > 1)
return n * factorial(n-1);
else
exit(EXIT_FAILURE);
/* fail - undefined */

Quote:
}

--

Sun, 02 Mar 2003 22:13:52 GMT  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* (n-1)!

int factorial (int n)
{
if n=1 return 1;
else return n*factorial(n-1);

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

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 N-1 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  Help with an algorithm in C

[ in too big a hurry ]

Quote:
> We can also use the fact that n! = n* (n-1)!
> int factorial (int n)
> {
> if n=1 return 1;
> else return n*factorial(n-1);
> }
> 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 n-1.

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(n-1)*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

 Page 1 of 5 [ 61 post ] Go to page:     

Relevant Pages

Powered by phpBB® Forum Software